백준 파이썬 2579 계단 오르기

 

🚀접근하기

다이나믹 프로그래밍 문제. 사실 전부터 다이나믹 프로그래밍 문제를 어려워했었는데, 역시나 이번에도 오랜만에 하니 어려웠다.....

처음에는 정말 이상하게 접근하다가, 

계단이 4개 이상일 때부터 일정한 점화식이 세워짐을 알게 되었다.

마지막 계단(n) 을 기준으로 2가지의 경우가 생기는데,

1) n과 n-2 계단 선택

2) n과 n-1, n-3 계단 선택 

 

즉,

 

예제 입력대로 6개의 수가 10,20,15,25,10,20 순으로 배열에 입력되었을 때, 

마지막인 6번째 계단을 기준으로 

1) 6번째 계단과 4번째 선택한 경우

2) 6번째 계단과 5번째, 3번째 계단을 선택한 경우

 

이렇게 두가지이다. 이 둘 중 max 값을 선택하여 더해주면 된다.

 

점화식: dp[n] = stairs[n] + max(stairs[n-1] + dp[n-3], dp[n-2])

 

🎉코드

 

n = int(input())

stairs = [0] * (n+1)
dp = [0] * (n+1)

for i in range(1, n+1):
    stairs[i] = int(input())


dp[1] = stairs[1]
if n >= 2:
    dp[2] = stairs[1] + stairs[2]
if n >= 3:
    dp[3] = stairs[3] + max(stairs[1], stairs[2])
    for i in range(4, n+1):
        dp[i] = stairs[i] + max(stairs[i-1] + dp[i-3], dp[i-2])

print(dp[n])

여기서 살짝 간과했던 부분이 if 문들을 작성하지 않았을 시에 n이 1인경우 index 에러가 발생한다는 것이다. 

따라서 if 문을 통해 조건을 나눠주었다.

 

dp[i] = stairs[i] + max(stairs[i-1] + dp[i-3], dp[i-2])

또한 여기서 i번째와 i-1번째는 dp가 아닌 stairs배열임을 헷갈려선 안된다!

 

💪다짐

점화식을 세우는 것을 잊지 말아야 겠다는 생각이 들었고,

일단 첫번째/두번째 케이스랑,  n번째 케이스의 경우가 다를 수 있으니 (예를 들어 n이 3일 때부터 일정한 점화식을 세울 수 있다던지) 항상 이를 생각해줘야겠다.

 

그리고 dp 배열을 따로 만들어서 dp 값들을 따로 저장해주기 !!