[백준] 2579번 계단 오르기 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

나의 풀이

n = int(input())
stairs = [0] * (n + 1)
d = [0] * (n + 1)

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

# 계단은 한 번에 한 개 or 두 개
# 세 개 연속 X
# 마지막 무조건 도착

if n == 1:
    print(stairs[n])

elif n == 2:
    print(stairs[1] + stairs[2])

else:
    d[1] = stairs[1]
    d[2] = stairs[1] + stairs[2]
    d[3] = max(stairs[2] + stairs[3], stairs[1] + stairs[3])


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

    print(d)

 

코드 설명 및 접근법

동적계획법의 핵심은 첫 몇 개의 케이스를 하드코딩해주고 나머지 경우들을 점화식을 통해 처리하는 것 같다.

 

연속된 세 개의 계단을 밟으면 안된다는 조건 때문에 분기문을 사용해야하나 고민했지만, 그럴 필요 없이 경우의 수 두 가지를 만들어 점화식으로 세워주면 꽤 쉽게 해결되는 문제였다.

 

여기서 경우의 수란, 계단을 어떻게 올라갈지에 대한 경우의 수가 아닌 어떻게 올라왔는지에 대한 경우의 수이다.

 

i 번째 계단에 도달했다고 가정할 때, 이전에 밟은 계단의 경우의 수는 2가지가 존재한다.

 

i - 3번째 계단을 밟고, i - 2번째 계단을 밟은 후 i 번째 계단에 도달한 경우와

 

i - 1번째 계단을 밟고, i 번째 계단에 도달한 경우이다. (이 경우에는 i - 2번째 계단을 밟지 않은 것으로 간주한다)

 

그리고 이 두 가지 경우의 수 중 더 큰 값을 리스트에 기록해주면 된다.

 

 

* 3번째 계단까지는 하드코딩을 해주었기 때문에, n의 값이 1이나 2가 들어올 경우 예외처리를 해주지 않으면 인덱스 에러가 난다.