2579 계단 오르기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())
graph = [0] * (301)
for i in range(1, N+1):
    graph[i] = (int(read()))

dp_table = [0] * (N+1)
dp_table[1] = graph[1]

if N == 1 :
    print(dp_table[1])

elif N == 2 :
    print(max(graph[2]+graph[1], graph[2]))

elif N == 3 :
    print(max(graph[3]+graph[1], graph[3]+graph[2]))

else :

    dp_table[2] = max(graph[2]+graph[1], graph[2])
    dp_table[3] = max(graph[3]+graph[1], graph[3]+graph[2])

    for i in range(4, N+1):
        dp_table[i] = max(graph[i]+dp_table[i-2], graph[i]+graph[i-1]+dp_table[i-3])

    print(dp_table[N])

3. 문제 풀이

이 문제는 쉬운거 같으면서도 좀 생각을 해야했다. 3칸이 연달아서 사용 불가능하다고 하니.. 그럼 조건문을 세워야하나..? 싶었지만, DP문제에서 조건문 따위 사치인 듯 하다. 점화식으로 푸는 해법은 3칸까진 1->3, 2->3 의 경우의 수로 나누고, 4칸째부턴 점화식을 세우는 것이다.

4칸째엔 2->4 또는 3->4 의 경우가 있는데, 2->4의 경우엔 2칸째의 최대 값을 dp table에서 찾고, 3->4의 경우엔 연속해서 밟으면 안되므로 dp_table[1]->3->4로 생각을 해야한다. dp_table[1]로 한 이유는 3번째 칸에서 두칸 떨어진 1번째 칸에서는 무슨일이 일어나더라도 상관이 없기 때문이다.

따라서 위에 코딩에 한 것처럼

\[dp\_table[i] = max(graph[i]+dp\_table[i-2], \\ graph[i]+graph[i-1]+dp\_table[i-3])\]

을 적용할 수 있다.