[DP] [BOJ 2579] 계단 오르기

 

2579번: 계단 오르기

문제

 

계단을 한 번에 최대 2칸까지 올라갈 수 있을 때, (연속된 세 칸을 밟을 수 없다.) n번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 구하는 문제

 

해석

이 문제에서 "N 번째 계단에서 얻을 수 있는 최대 점수"는 규칙에 따라서 두 가지로 나누어볼 수 있다.

 

1. N-1번째 계단에서 N번째 계단으로 넘어온 경우

2. N-2번째 계단에서 N번째 계단으로 넘어온 경우

(N번째 계단에 오르는 문제를 더 작은 문제로 분할하고, 이로부터 더 큰 문제를 해결할 수 있기 때문에

DP로 해결할 수 있다.)따라서 처음에 이 문제를 보면 식을 이렇게 세우게 된다.

 

d :  N에 따른 정답을 저장하는 배열

score: N번째 정답에서 얻을 수 있는 점수

d[N] = MAX(d[N-1], d[N-2]) + score[N]

 

하지만 이 문제에 있는 "연속된 세 계단을 밟으면 안된다"는 조건이 이 문제를 어렵게하는데, [N-1] -> [N]으로 넘어오는 경우 중에서, 그림에서 처럼 [N-2] -> [N-1] -> [N]를 제외해야한다. [N-1] -> [N]으로 넘어오는 경우는 두 가지 방법 ([N-3] -> [N-1] -> [N], [N-2] -> [N-1] -> [N])이 있으므로, 나머지 하나인 [N-3] -> [N-1] -> [N] 이렇게 넘어오는 경우만 세어주면 된다. (이해가 잘 되지 않는다면 그림을 다시 보자.)

 

따라서 식은 다음과 같이 세워야 한다.

d[N] = MAX(d[N-2], d[N-3] + score[N-1]) + score[N])

 

구현