[백준 2579번] 계단 오르기

n = int(input())

score = [0]*n
dp = [0]*n

for i in range(n):
    score[i] = int(input())

if n == 1:
    print(score[0])
elif n == 2:
    print(score[0]+score[1])
elif n == 3:
    print(score[0]+max(score[1],score[2]))
else:
    dp[0] = score[0]
    dp[1] = score[0] + score[1]
    dp[2] = score[2] + max(score[1],score[0])
    
    for i in range(3,n):
        dp[i] = score[i] + max(score[i-1] + dp[i-3], dp[i-2])

    print(dp[n-1])

이번 문제는 다음과 같은 3가지 조건들을 만족하면서 계단을 오를 때 얻을 수 있는 점수의 최댓값을 구하는 문제이다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

처음에는 마지막 도착 계단을 반드시 밟아야한다는 조건에 휘둘려 마지막 계단부터 시작하여 풀이하였는데, 결국 이 방법으로 1시간동안 헤메다가 조건들이 너무 많아서 뭔가 접근이 잘못 되었다는 생각이 들었다.

 

다시 초심으로 돌아가 앞에서 부터 DP 알고리즘을 사용하여 풀어보기로 하였는데, 여기서 가장 중요한 핵심은 '점화식을 도출해내는 것'이었다.

 

먼저 DP 리스트(dp)를 선언 및 초기화하고 첫번째부터 세번째 값까지 저장 한뒤에, 연속된 3개의 계단을 밟는 것이 불가능하기 때문에 DP리스트에 DP[i] = score[i] + max(DP[i-3] + score[i-1], DP[i-2]) 라는 점화식을 활용하여 풀이할 수 있었다.

 

DP를 활용하여 풀이하는 문제는 작은 값부터 패턴이 보일 때까지 적어본 뒤에, 점화식을 도출해야 한다는 것을 뼈저리게 느낄 수 있었던 문제였다 :)

 

 

DP는 결과 값을 얻기 위한 과정을 쌓아가는 것이다.
이전 결과 값을 활용하여 N번째에서 최선의 값을 얻을 수 있다.