[ BOJ 오답노트 ] 2579 파이썬 : 계단 오르기

2022 03 24

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 도저히 생각이 안났다. 일단 한 칸 오르고 또 한 칸 오르는 것이 불가능하다는 조건을 어떻게 따져야 할 지 고민이었다.

- 맨 앞에서부터 따질 지, 맨 뒤에서부터 따질 지 고민했다.

- 두 칸을 건너 뛰면 i의 값을 +2 해주어야 하는지 등 고민을 했고, 문제가 풀리지 않아서 다른 분들의 정답 코드를 확인했다.

 

 

 

3. 해결

import sys
input = sys.stdin.readline

n = int(input())
stairs = [0]    # 1번부터 n번까지의 index를 사용하기 위해서
dp = [0]*(n+1)

for _ in range(n):
    stairs.append(int(input()))

if n == 1:
    print(stairs[1])
else:
    dp[1] = stairs[1]
    dp[2] = stairs[1] + stairs[2]

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

    print(dp[n])

 

 

 

4. 배운 점

- 정말 DP의 세상은 한계가 없구나..ㅎ

- DP는 모든 인덱스 값을 저장한다. 각각의 인덱스 값이 쓰일 지 말 지, 그리고 어떤 경우에 쓰고 비교하는 지가 핵심이라고 생각한다.