[Python 3] BOJ - 2579 "계단 오르기"

 # 문제 링크 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 # 풀이 :

개인적으로 문제의 핵심은 다이나믹 프로그래밍을 이용하는 것, 이 문제에서는 현재 계단에 올라가기 위해 이전계단에 대한 경우를 계산하는 것이라고 생각한다. 배열 D[0][i]를 i번째 계단으로 한칸 이동하여 갈 때 얻을 수 있는 최대 점수라고 정의하고, D[1][i]를 i번째 계단으로 두칸 이동하여 갈 때 얻을 수 있는 최대 점수라고 정의하자.

<그림 1. 각 계단에 대한 경우의 수>

 현재 계단이 5개 있고 빨간색 계단, 즉 3번 계단을 오르는 경우를 가정해보자. 갈 수 있는 방법의 수는 1번 계단에서 2칸을 오르거나, 2번 계단에서 1칸을 오르는 경우 2가지다. 그렇다면, 파란색의 2번 계단을 갈 수 있는 방법의 수는 1번 계단에서 1칸을 오르는 경우거나, 바닥에서 2칸을 오르는 경우다. 이때, 2번에 오른 경우가 1번계단에서 한 칸 오른 경우라면, 2번 계단에서 3번을 갈 때는 한 칸 오른 경우로 갈 수 없다. 왜냐하면 연속되는 세 계단을 오를 수 없다는 문제의 조건을 위배하기 때문이다. 

 따라서, 어떤 i번째 계단을 2칸을 통해 갈 수 있는 방법은 i - 2번째 계단에서 부터 출발하는 것이다. 그런데, 그 i - 2번째 계다에서 2칸을 통해 i번째 계단으로 올라간 것은 동일하나, 점수가 달라지기에 i - 2번째를 이전 단계(i - 3)에서 1칸을 통해 올라왔을 때의 점수와 이전 단계(i - 4)에서 2칸을 통해 올라왔을때의 점수 중 큰 값이 i번째 계단을 2칸 통해 올라 갈 수 있는 방법, 즉 D[1][i]가 된다.

<그림 2. 2칸 이동할때의 일반적 상황>

 반대로 i번째 계단을 한칸만 이동하여 갈 수 있는 경우를 생각해보자. 이는 굉장히 간단한데, i - 1번째 계단에서 올라가되, i - 1번째 계단이 이전단계에서 2칸 이동하여 도착한 경우만 가능하다. 만일, i - 2에서 1칸 이동하여 i - 1로 이동하고 다시 i - 1에서 한 칸 이동하여 최종적으로 i에 도착한다면 '연속한 세 계단을 밟아서는 안된다'는 조건을 위배하므로 i - 3에서 두 칸 이동하여 i - 1을 밟아야 연속성이 깨지기 때문에 한 칸을 이동하여 i번째를 밟아도 조건을 위배하지 않는다.

위의 모든 내용을 점화식으로 표현하면 아래와 같다.

<그림 3. 점화식>

 # 코드

import sys

# 입력부
num = int(sys.stdin.readline())
a = [0] * (num + 1)
for i in range(1,num + 1):
    temp = int(sys.stdin.readline())
    a[i] = temp
    
# 계단이 하나인 경우
if num == 1:
    print(a[1])
else:
    d = [[0] * (num + 1) for _ in range(2)]
    # 바닥에서 1을 가는 경우, 바닥에서 2를 가는 경우 예외처리
    d[0][1] = a[1]
    d[1][2] = a[2]
    for i in range(2, num + 1):
        d[1][i] = max(d[1][i - 2] + a[i], d[0][i - 2] + a[i])
        if i == 2:
            # 2번째 계단은 반드시 1번째 계단을 한 칸 올라간 경우에서 올라와야 하므로 예외처리
            d[0][i] = d[0][i - 1] + a[i]
        else:
            d[0][i] = d[1][i - 1] + a[i]

    print(max(d[0][num], d[1][num]))