[BOJ] 2579. 계단 오르기

Python3,DP

문제

입출력

입출력 예시

나의 풀이 (시도)

n = int(input())

dp = [0] * n
w = [0] * n

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

dp[0] = w[0]   
dp[1] = w[0] + w[1]
dp[2] = max(w[0] + w[2], w[1] + w[2])

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

컴파일러에서는 오류 없이 잘 출력됐는데 백준 사이트에서는 계속 틀렸다고 떴다.
게시판에 있는 모든 반례를 넣어 봐도 잘 떴다..
근데 max를 써서 푸는 문제가 아니라 n-1번째에 있는 dp값을 출력해야 하나 보다.
그래서 찾다가 코드를 수정했다.

주요 포인트

2156번 포도주 마시기 문제와 비슷하다.

마지막 계단은 꼭 밟아야 한다. 따라서 두 가지로 나눌 수 있는데

1) 전 계단을 밟은 경우
2) 전 계단을 밟지 않은 경우

밟은 경우는 dp[i-3] + w[i-1] + w[i] 로 나타낼 수 있고,
밟지 않은 경우는 dp[i-2] + w[i] 로 나타낼 수 있다.

두 수 중 더 큰 값을 dp에 넣는다.

최종 코드

n = int(input())

dp = [0 for i in range(301)]
w = [0 for i in range(301)]

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

dp[0] = w[0]   
dp[1] = w[0] + w[1]
dp[2] = max(w[1] + w[2], w[0] + w[2])

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

피드백

컴파일러에서는 오류가 안 떠서 한참 헤맸다. 가장 큰 값을 출력하는 것이 아니라 가장 마지막에 있는 dp 값을 출력한다.