[Baekjoon] # 2579 계단오르기

문제

문제 보기

문제

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

<그림 1>

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

<그림 2>

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

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

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

입력

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

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

출력

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

예제 입력 1 복사

6
10
20
15
25
10
20

예제 출력 1 복사

75

풀이

동적계획법에 따른 규칙 탐색(Bottom-up 방식)

계단갯수가 1개인 경우부터, 천천히 정답을 도출하며 규칙을 찾는다.
계단이 1개라면, 그 계단의 점수가 곧 정답이다.
계단이 2개라면, 두 계단의 점수합이 정답이다.
계단이 3개라면, 1번째+3번째 점수합 vs 2번째+3번째 점수합을 비교하여 더 큰 값이 정답이다.

계단이 4개라면, 다음 두가지 경우의 수를 비교하여야 한다.
1) 2번째 계단을 밟고 4번째(마지막) 계단을 밟는다.
2) 1번째 계단을 밟고, 3번째(마지막 직전)와 4번째(마지막) 계단을 연달아 밟는다.

즉, n개의 계단들의 점수 배열을 score, 가능한 점수최대값을 f(n)이라 하면, 다음과 같은 수식으로 규칙을 정리할 수 있다.
f(n) = max(f(n-2)+score[-1], f(n-3)+score[-2]+score[-1])

위처럼 발견한 규칙성을 그대로 코드로 구현하면 된다.

코드

# 입력부
n = int(input())
score = []
for i in range(n):
    score.append(int(input()))

# 함수부
def solution(score):
    if len(score) == 1:
        return score[0]
    elif len(score) == 2:
        return score[0]+score[1]
    elif len(score) == 3:
        return score[2]+max(score[0], score[1])
    
    # Memoization
    res = [score[0], score[0]+score[1], score[2]+max(score[0], score[1])] 
    
    for i in range(4, len(score)+1):
        res.append(max(res[i-3]+score[i-1], res[i-4]+score[i-2]+score[i-1]))
    return res[-1]

answer = solution(score)
print(answer)

중복된 계산을 최소화하기 위하여 Memoization 역할을 수행할 리스트(res)를 만들어 계산값을 저장한다.

계단의 길이(`len(score)`)가 3이하인 경우, 일일히 값을 지정하여 반환한다.

계단의 길이가 4이상인 경우, 앞서 구한 규칙성을 바탕으로 최대값을 계산하여 차례차례 res에 값을 추가한다.

• 최종적으로, res의 마지막 값을 반환하면 정답이다.