[백준 2579] 계단오르기 - 동적계획법1

이것도 이전 문제처럼 혼자 힘으로 풀 수 있을 줄 알았다. 

일단 애초에 절대 혼자 못 풀었고, 구글링으로 힌트라고 해야하나, 코드만 안 봤지 코드 동작방식 설명을 보고 풀었다.

그리고 첫 계단을 안 밟아도 된다는 걸 몰랐다. 아무리 생각해도 답이 맞았는데 자꾸 틀렸대서 질문검색을 해보고 알았다.

계단은 '한 계단을 밟으면서' 오를 수 있다길래 첫 계단은 기본인 줄 알았다. ....

 

어쨌든 코드 동작방식을 보고 그대로 구현한 코드는 다음과 같다.

n = int(input())
st = [int(input()) for _ in range(n)]

dp = st[:1] + [0]*(n)
for i in range(1,n):
    dp[i] = max(st[i]+st[i-1]+dp[i-3], st[i]+dp[i-2])
print(dp[n-1])

이 간단해 보이는 코드를 얼마나 오래 생각했는지. 

아이디어 자체가 떠오르지 않았다. 너무 이전 문제들에 시야를 가두고 있었나보다.

(알고나니) 동작방식은 간단하다.

1. 현재 위치 점수 + 1번째 이전 위치 점수 + 3번째 이전 위치까지의 점수 (계단을 3개 연속 밟을 수 없으니)

2. 현재 위치 점수 + 2번째 이전 위치까지의 점수

이 둘 중 더 큰 걸 더해나가면 된다. 

그러니까 현재 위치까지 오는 방법 중 최댓값을 취하는 걸 반복하는 것이다. 그 방법이 위의 두 개뿐이다.

 

여기서 st[:1]은 첫 계단의 점수를 dp에 넣어준 것이다. 첫 계단은 무슨 일이 있어도 점수가 변하지 않기 때문이다.

그리고 dp 길이를 n으로 설정하지 않고 n+1로 설정한 이유는, n이 2인 경우를 위해서다. (이것만 온전히 내가 떠올린 것이다..)

그렇지 않고 아래 수식에 넣게 되면, 예를 들어 [10,20]인 경우 dp[2-3]은 20이 되어 계산이 잘못된다.

따라서 dp[-1]이 0이 되고 아래 수식이 정상적으로 동작할 수 있도록 dp 맨 뒤에 0을 넣어준 것이다.

if문을 사용해 n=2인 경우 print를 따로 지정해주거나 하는 방법도 있지만, 코드 결벽증인 나에겐 사치다.

dp 맨 뒤에 0을 넣어서 n=2인 경우에도 잘 동작하므로 반복문 범위도 (1,n)으로  설정했다.