[Baekjoon]2579.계단오르기(DP)

Baekjoon

#2579. 계단오르기

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

---

문제를 처음 읽었을때 포도주 시식 문제와 비슷한 문제라고 느꼈다. 다른 점은 이 문제는 종점이 마지막 계단으로 정해져 있다. 마지막 계단을 n번째 계단이라고 하고 n번째 계단에 도착하는 방법을 생각해 보면 다음과 같다.

1. 바로 이전 계단을 밟지 않고 오는 경우.

2. 바로 이전 계단을 밟고 오는 경우. 

1에서 바로 이전 계단을 밟지 않고 왔다는 것은 전전계단은 반드시 밟았어야 한다.(1칸이나 2칸씩만 올라갈 수 있으므로 !! 이 경우 두칸을 올라온 것임). 1 에서 바로 이전 계단을 밟고 왔다는 것은 두 계단을 연속으로 밟은 것이므로 전전계단은 반드시 밟지 않았어야 한다. 

빨간색칸이 밟지 않고 온 칸이다. 먼저 d[n]을 정의하면

d[n] : n번째계단까지 올 때 얻을 수 있는 최대 점수

위 그림에서 n번째 계단에 도착할 수 있는 방법을 점화식으로 나타내면 다음과 같다.

1. d[n][1] = max(d[n-2][1], d[n-2][2]) + a[i]

2. d[n][2] = d[n-1][1] + a[i]

1은 n-1번째 계단은 밟을 수 없으므로 n-2번째 계단까지 얻을 수 있는 최대 점수에 n번째 계단의 점수를 더한 값이 방법1의 최댓값이다. 2는 n-1번째 계단을 밟아야하므로 n-2번째 계단은 밟지 않았어야한다. 바로 이전 계단을 밟지 않고 오는 방법은 방법1 이므로 d[n-1][1]의 의미가 n-2번째 계단을 밟지 않고 n-1번째 계단까지 올때 얻을 수 있는 최대 점수이다. 따라서 이 값에 a[i]를 더한 값이 방법2의 최댓값이다.  

구하고자 하는 답은 방법1과 방법2 중 최댓값이므로 max(d[n][1], d[n][2])가 문제의 정답이다. 나는 2차원 배열을 사용하여 d를 만들었고 d[i][0]에 방법1, d[i][1]에 방법2 의 값을 저장했다. 처음에 포도주 시식 문제와 비슷하게 생각해서 1번연속 한칸으로 오는 경우, 2번연속 한칸으로 오는 경우, 2칸으로 오는 경우 이렇게 3가지로 생각했었는데 1칸을 올라와서 도착하는 것이 이미 현재 계단과 이전 계단을 밟아서 온 것이므로 처음 생각했던 방식은 오류가 있었음을 알았다. 

<전체 코드>