[파이썬, Python] 백준 2579: 계단 오르기

문제

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

2579번: 계단 오르기

코드

n = int(input())
score = [0 for _ in range(n+1)]
stair = [0 for _ in range(n+1)]
for i in range(1, n+1):
    stair[i] = int(input())


score[1] = stair[1]

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

설명

직관적이지 않은 다이내믹 프로그래밍을 구현하는 문제이다.

각 계단에 도착했을 때의 최대 점수를 찾는 방식으로 풀어나가면 된다.

우선 점수와 계단의 리스트를 생성해 준다.
이후 계단의 리스트에 각 계단의 점수를 추가해 준다.

첫 계단을 밟았을 때의 점수는 첫 계단의 점수와 동일하므로 미리 지정해 준다.
이후 2번째 계단부터 계산을 하게 되는데,
2번째 계단의 최대 점수는 1번째와 2번째 모두 밟은 경우이므로 이를 입력해 준다.

3번째 계단부터는 경우의 수를 고려해야 한다.
연속해서 3 계단을 밟지 못하므로, 3번째 계단에 올라올 수 있는 경우의 수는
1번과 3번 계단 혹은 2번과 3번 계단 2가지의 경우가 있다.
이를 반영하여 두 수치 중 더 큰 수치를 입력해 준다.

나머지의 경우는 4번 계단으로 예시를 들어서 설명을 하면,
4번 계단을 올라오며 가능한 경우의 수는
1번 3번 4번, 혹은 1번 2번 4번의 경우가 있다.
이 중 1번 2번 4번을 밟는 경우는 1번과 2번을 밟은 점수가 2번에 기록되어 있으므로 이를 사용하여 점수를 계산해준다.

이후 스코어를 출력해주면 된다.