[백준] 2579 계단 오르기

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력

6
10
20
15
25
10
20

예제 출력

75

풀이

RGB거리 문제와 유사한 문제이다. 고려해야할 점은 다음과 같다

K번째 계단은 K-1,K-2번째 계단까지의 최댓값을 비교하여 더 큰 값을 선택해야 한다. 이때 K번째 계단은 K-1번째 계단과 이어진 경우 K-1번째 계단이 K-3번째 계단과 이어진 경우를 선택해야 하고, K-2번째 계단과 이어진 경우는 K-2번째 계단이 K-3,K-4번째 계단과 이어진 각각의 최댓값 중 더 큰 값을 선택하면 된다.

이게 반복되는 과정이기 때문에 결국 K번째 계단에서 K-1,K-2번째 계단까지의 K-2, K-3과 이어진 경우와 K-3,K-4로 이어진 경우의 최댓값들을 모두 알고 있어야 한다.

DP - Bottom up 방식

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

if n == 1: print(arr[1])
elif n == 2: print(arr[1]+arr[2])
else:
    check = {} # 키: 인덱스, 값: 배열[2칸 전 값, 1칸 전 값]
    check[1] = [arr[1]]
    check[2] = [arr[2], arr[2]+arr[1]]
    check[3] = [arr[3]+arr[1], arr[3]+arr[2]]

    for i  in range(4, n+1):
        check[i] = [arr[i]+max(check[i-2]), arr[i]+check[i-1][0]]
    print(max(check[n]))

점화식

점화식을 염두에 두긴 했지만 생각나지 않아 단순히 동작 원리를 생각하여 코드를 짰더니 풀긴 했지만 시간이 많이 걸렸다. 다른 분들의 풀이에서 점화식을 발견하여 적고자 한다.

f(n)
= n번째까지의 최댓값
= MAX(n-1번째까지의 최댓값 + n번째 값, n-2번째까지의 최댓값 + n번째 값)
= MAX(n-3번째까지의 최댓값 + n-1 번째 값 + n번째 값, n-2번째까지의 최댓값 + n번째 값)
= MAX(f(n-3) + stair[n-1] + stair[n], f(n-2) + stair[n])

여기서 주의할 점은 f(n) 점화식 내에서 n-1번째까지의 최댓값을 구할때 f(n-1)을 사용하는게 아니라, f(n-3) + n-1번째 값 을 사용해야 한다는 점이다.

왜냐하면 n-1번째까지의 최댓값은 n-2번째 계단과 연결되거나 n-3번째 계단과 연결되는 2가지 종류가 존재하는데 우리는 무조건 n-3번째 계단과 연결되는 경우에 대해서만 고려해야 하기 때문이다.

DP - Bottom up 방식(점화식 이용)

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

if n == 1: print(arr[1])
elif n == 2: print(arr[1]+arr[2])
else:    
    dp = [0] * (n+1)
    dp[1],dp[2],dp[3] = arr[1], arr[1]+arr[2], max(arr[1]+arr[3], arr[2]+arr[3])
    for i  in range(4, n+1):
        dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2]+arr[i])
    print(dp[n])