[백준][DP] 2579 : 계단 오르기

문제

https://www.acmicpc.net/problem/2579

필요 지식

 - dynamic programming

해결 방법

 - 2개의 배열이 필요 : cost, sub

     - cost : 입력 값 (그 계단의 점수)

     - sub : 현재 계단오기까지 최대 점수 합

참고로 시작점을 배열 제일 처음으로 정한다. 즉, cost[0] = sub[0] = 0이다.

계단1로 가기 위해서는 그냥 계단 1의 점수를 얻는 상황만이 가능하다.

sub[1] = cost[1]

계단 2로 가기 위해서는 계단 1을 거치고 가거나, 계단 2로 바로 점프하는 2가지 경우가 있지만, 계단 1을 거치는 것이 당연히 점수가 높다. 왜냐하면, 계단 1을 거치고 가면 (0 > 1 > 2)이고, 계단 1의 점수와 계단 2의 점수 둘다 합치는 것이고, 계단 2로 바로 점프하면 (0 > 2)이고, 계단 2의 점수만 있기 때문이다. 따라서, 계단 2로 가기 위해서는 최대 값이 (0 > 1 > 2)이다.

sub[2] = cost[1] + cost[2]

계단 3으로 가기 위해서는 두가지 상황이 가능하다.

1인 계단에서 오거나, 2계단에서 오는 경우의 상황이 있다.

(0 > 1 > 3) /  (0 > 2 > 3)

하지만, 2계단에서 올 경우, 1계단을 거쳐서 오면 안된다. 즉, (0 > 1 > 2 > 3)은 안된다는 것.

2계단에서 올 경우, 전 전인 0계단에서 점프해서 오는 것이다.

일단 보류하고, 계단 4로 가기 위한 방법을 생각해보자.

계단 4로 가기 위해서도 2가지 상황이 가능하다.

2인 계단에서 점프해서 오거나, 3계단에서 바로 오는 경우.

전체 경우를 본다면, (0 > 1 > 2 > 4), (0 > 2 > 4) /  (0 > 1 > 3 > 4)

3계단에서 바로 오는 경우는 2계단을 거쳐서 오면 안된다.

그렇다면 3계단을 오기 위해 1계단에서 오는 경우를 생각하는 것이다. 

조금 더 명확히 하기 위해, 계단 6으로 가는 방법을 생각해보자.

이 경우도, 계단 4에서 오거나 계단 5에서 오면 된다.

전체 경우를 본다면,

계단 4에서 오는 경우 : (0 > 1> 2 > 4 > 6), (0 > 1 > 3 > 4 > 6), (0 > 2 > 4 > 6)

계단 5에서 오는 경우 : (0 > 1 > 3 > 5 > 6), (0 > 1 > 3 > 5 > 6)

이 경우에도 계단 5를 가기 위해서는 계단 4를 거치지 않아야 하기에 계단 3까지 온 다음 점프해서 5로 가야 한다.

즉, 쉽게 생각한다면, 계단 6까지 오는 방법은 계단 4까지 오는 모든 방법 중 최대가 나오는 방법에서 점프하거나, 계단 3까지 오는 방법 중 최대가 나오는 방법에서 점프해 5로 가고 6으로 가는 것이다. 그 중 최대인 것이 계단 6까지 오는 방법의 최대값이 된다. 어차피 두 방법 모두 6으로 가는 것은 공통이므로, 공통인 부분을 따로 더하면 됨.

식으로 나타낸다면,

sub[6] = max( sub[4], sub[3] + cost[5]) + cost[6]

즉, 일반화를 한다면,

i번째 계단까지 오는 최대 값은 i-2번째 계단까지 오는 최대와 i-3번째 계단까지 오는 최대에다 i-1계단의 값을 더한 값 중 더 큰 값을 고르고, 거기다 현재 i번째 계단의 점수를 더하는 것이다.

식으로 나타낸다면 밑과 같게 된다.

sub[i] = max( sub[i-2], sub[i-3] + cost[i-1]) + cost[i]

즉, sub[1], sub[2]는 앞서 서술한대로 값을 지정해 준 후, sub[3]부터는 위의 식을 적용하면 된다.

주의할 점

 - n이 1로 주어졌을 때를 생각하기

• 다른 사람의 풀이를 보니 백준에서 n=1일때 경우의 테스트 케이스는 만들지 않은 것 같다.
• 하지만, 문제 조건에서 n은 자연수라고 했으니 n=1인 상황이 가능하다.
• 따라서, n=1일 때, sub[2]에 값을 넣으려고 sub[2]로 접근하려 한다면, 메모리 할당관련 오류가 생길 수 있다.
• 그러므로, 안전장치인 if(n>1)을 넣어야 한다.

코드