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

2024년 4월 11일

문제 링크 : 백준 2579번 - 계단 오르기

2579번: 계단 오르기

 

문제

 

 

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

<그림 1>

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

<그림 2>

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

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

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

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

입력

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

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

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

---

문제 접근

 

전형적인 DP 문제라고 판단되어 빠르게 점화식을 찾아야겠다고 생각했다.

 

먼저, 이 문제에서 유도된 점화식은 다음과 같다.

 

N = 현재 계단 번호
stair[N] : N번째 계단의 점수

dp[N] = N번째 계단이 가지고 있는 최댓값 경우의 수 2가지.
dp[N][0] = N번째 계단을 연속 1개 째 밟은 상태의 최댓값
dp[N][1] = N번째 계단을 연속 2개 째 밟은 상태의 최댓값

위와 같이 정의할 수 있을 때, 특정 계단 T가 가질 수 있는 최댓값 경우의 수 dp[T]를 구하면 다음과 같다.

1. dp[T][0] = MAX( dp[T - 2] ) + stair[T]
2. dp[T][1] = dp[T - 1][0] + stair[T]

만약, T번째 계단을 밟았을 때 가질 수 있는 점수의 최댓값은 다음과 같다.

MAX(dp[T])

 

위 점화식 유도 과정은 뒤에서 설명하며 한번 더 언급할 것이다.

 

 

이 문제에서 우리가 고민해야 하는 부분은 다음과 같다.

 

1. 한 번에 계단은 1개 혹은 2개 오를 수 있다.

2. 하지만 3개의 계단을 연속해서 오를 수는 없다.
1번 계단을 밟고 2번 계단을 밟은 상태에서, 바로 다음 계단인 3번 계단은 오를 수 없다는 뜻이다.

 

위 부분을 유념하며 입력 예시를 가지고 원하는 출력 값을 유도해보자.

 

 

1. 첫 번째 계단 오르기

 

첫 번째 계단을 오르는 경우

 

우리는 지금부터, 각 계단 별로 가질 수 있는 최댓값을 저장해둘 것이다.

 

각 계단 별로 길이가 2인 배열을 지닐 것이며,

각 계단이 지닌 배열의 0번째 인덱스는 현재 계단이 연속 1개 째 밟고 있는 상태를 의미하고

각 계단이 지닌 배열의 1번째 인덱스는 현재 계단이 연속 2개 째 밟고 있는 상태이다.

(이 부분을 잘 기억해두자)

 

이렇게 나눈 이유는 연속해서 3개의 계단을 밟을 수 없다는 문제의 조건 때문이다. (자세한 이유는 뒤에서 자세히 설명할 것)

위와 같이 구분을 시킨다면 현재 계단에서 다음에 밟을 계단을 모색할 때, 다음 계단을 밟는 경우 중 3번 연속 계단을 밟는 경우는 제외시키기에 용이하다.

 

시작점은 점수가 없기에 초기값은 0으로 세팅하였다.

첫 번째 계단을 오르는 경우의 수는 시작점에서 한 칸 계단을 오르는 경우밖에 없다.

연속해서 1개 계단을 오른 상태밖에 존재하지 않는다. 그러므로 첫 번째 계단에 [0 + 10, 0]의 배열 값을 저장해둔다.

 

 

2. 두 번째 계단 오르기

 

두 번째 계단을 오르는 경우

 

두 번째 계단을 오르는 경우의 수는 2가지로,
2개 전 계단(시작점)에서 두 칸 오르는 경우( ① ) 와 1개 전 계단에서 한 칸 오르는 경우( ② )이다. 

 

2개 전 계단에서 두 칸 오르는 경우 ( ① ) 는 2개 전 계단이 가지고 있는 2가지 경우의 최댓값 각각에 현재 계단의 점수를 더한 값 중 더 큰 값을 고르면 된다. 

어차피 두 칸 올랐으니 현재 밟고있는 계단은 연속 1개의 계단을 오른 상태이므로 2가지 경우에서 더 큰 값을 현재 밟고있는 계단의 0번째 인덱스에 값을 저장해두면 된다.

 

1개 전 계단에서 한 칸 오르는 경우 ( ② ) 는 ① 과 같이 1개 전 계단이 가지고 있는 2가지 경우의 최댓값 각각에 현재 계단의 점수를 더한 값 중에 더 큰 값을 고르면 될 것 같지만, 아니다!  

 

연속으로 2개의 계단을 오른 상태가 아닌 경우의 수에서 현재 계단의 점수를 더해야 한다.

연속으로 2개의 계단을 오른 상태에서 바로 다음 계단인 현재 계단을 밟게 되면 문제에서 제시한 연속 3개의 계단을 오를 수 없다는 전제에 어긋나기 때문.

 

일단 현재 계단인 두 번째 계단을 밟았을 때에는 연속 3개의 계단을 오르는 경우는 존재하지 않기 때문에 일단 이전 계단이 가지고 있는 최댓값에서 현재 계단의 점수를 더해준다. " 연속으로 2개의 계단을 오른 상태가 아닌 경우의 수에서 현재 계단의 점수를 더해야 한다." 는 부분은 다음 단계인 세 번째 계단 오르기에서 자세히 설명하도록 하겠다.

 

이 결과는 각각 위 그림과 같이 현재 계단에 [20, 30]의 배열 값을 저장하게 된다.

 

각각 현재 계단에 오른 경우의 수 중, "연속 1개의 계단을 오른 경우의 최댓값은 20" 이며 "연속 2개의 계단을 오른 경우의 최댓값은 30" 이라는 의미를 지니고 있다.

 

 

3. 세 번째 계단 오르기

 

세 번째 계단을 오르는 경우

 

세 번째 계단을 오르는 경우의 수 또한 위에서 정의한 2개 전 계단(시작점)에서 두 칸 오르는 경우( ① ) 와 1개 전 계단에서 한 칸 오르는 경우( ② )가 존재한다.

 

2개 전 계단(시작점)에서 두 칸 오르는 경우( ① )는 2개 전 계단인 첫 번째 계단이 가지고 있는 2가지 최댓값에 각각 현재 계단의 점수를 더해 그 중 더 큰 값을 0번째 인덱스에 저장해두면 된다.

 

1개 전 계단에서 한 칸 오르는 경우( ② ) 또한 ① 처럼 1개 전 계단인 두 번째 계단이 가지고 있는 2가지 최댓값에 각각 현재 계단의 점수를 더해 그 중 더 큰 값을 1번째 인덱스로 저장하면 될 것 같지만, 그러면 오류를 범한다.

무슨 오류? 연속 3개의 계단을 오를 수 없다는 전제에 어긋나는 오류.

 

이전 계단의 0번째 인덱스에 현재 계단의 점수를 더한다는 것은 무엇을 의미하는가?

이전 계단을 밟은 경우의 수 중 연속 1개의 계단을 밟았을 때 현재 계단을 이어서 밟은 경우이므로 현재 계단을 밟았을 때, 연속 2개의 계단을 밟은 상태를 의미한다.

 

이 부분은 문제가 없다.

 

이전 계단의 1번째 인덱스에 현재 계단의 점수를 더한다는 것은 무엇을 의미하는가?

이전 계단을 밟은 경우의 수 중 연속 2개의 계단을 밟았을 때 현재 계단을 이어서 밟은 경우이므로 현재 계단을 밟았을 때, 연속 3개의 계단을 밟은 상태를 의미한다.

 

이 경우를 제외시켜야 한다. 

 

계단을 2번 연속 오른 경우의 최댓값에 현재 계단의 점수를 더하면 안된다.

 

 

그렇다면 현재 계단의 1번째 인덱스에 저장할 값은 이전 계단을 올랐을 때 연속 1개의 계단을 오른 경우의 최댓값 + 현재 계단의 점수이다.

 

 

이로써, 유도된 점화식은 다음과 같다.

 

N = 현재 계단 번호
stair[N] : N번째 계단의 점수

dp[N] = N번째 계단이 가지고 있는 최댓값 경우의 수 2가지.
dp[N][0] = N번째 계단을 연속 1개 째 밟은 상태의 최댓값
dp[N][1] = N번째 계단을 연속 2개 째 밟은 상태의 최댓값

위와 같이 정의할 수 있을 때, 특정 계단 X가 가질 수 있는 최댓값 경우의 수 dp[X]를 구하면 다음과 같다.

1. dp[X][0] = MAX( dp[X - 2][0] + stair[X], dp[X - 2][1] + stair[X] ) = MAX( dp[X - 2] ) + stair[X]
2. dp[X][1] = dp[X - 1][0] + stair[X]

만약, X번째 계단을 밟았을 때 가질 수 있는 점수의 최댓값은 다음과 같다.

MAX( dp[X] )

 

이 점화식을 바탕으로 나머지 계단이 지니는 최댓값도 쉽게 구할 수 있다.

 

 

4. 네 번째 계단 오르기

 

네 번째 계단을 오르는 경우

 

2개 전 계단(시작점)에서 두 칸 오르는 경우( ① ) 와1개 전 계단에서 한 칸 오르는 경우( ② )가 존재하며,

 

① : dp[4][0] = MAX(dp[4 - 2]) + 현재 계단의 가치 = 55

② : dp[4][1] = dp[4 - 1][0] + 현재 계단의 가치 = 50

 

 

 

5. 다섯 번째 계단 오르기

 

다섯 번째 계단을 오르는 경우

 

2개 전 계단(시작점)에서 두 칸 오르는 경우( ① ) 와1개 전 계단에서 한 칸 오르는 경우( ② )가 존재하며,

 

① : dp[5][0] = MAX(dp[5 - 2]) + 현재 계단의 가치 = 45

② : dp[5][1] = dp[5 - 1][0] + 현재 계단의 가치 = 65

 

 

 

6. 여섯 번째 계단 오르기

 

마지막 계단인 여섯 번째 계단을 오르는 경우

 

 

2개 전 계단(시작점)에서 두 칸 오르는 경우( ① ) 와1개 전 계단에서 한 칸 오르는 경우( ② )가 존재하며,

 

① : dp[6][0] = MAX(dp[6 - 2]) + 현재 계단의 가치 = 75

② : dp[6][1] = dp[6 - 1][0] + 현재 계단의 가치 = 65

 

마지막 계단을 밟았을 때, 얻을 수 있는 점수의 최댓값을 구하는 문제이므로, MAX( dp[6] )인 75가 최댓값이 된다.

 

 

---

순서도

 

1. 입력값을 입력받아 각 계단의 가치를 지니는 stair 배열을 선언하여, 시작점을 뜻하는 0번째 인덱스에 0을 먼저 append한다.

2. 각 계단이 지니는 최댓값들을 저장할 dp를 선언한다.

3. 기저 조건인, 시작점(dp[0])과 첫 번째 계단(dp[1])은 특수케이스로 저장한다. 각각 [0, 0] , [1번째 계단의 가치, 0] 이다.

4. 2번째 계단부터 점화식을 바탕으로 최댓값 조합을 구하며 마지막 계단까지 최댓값 조합을 구한다.

5. 마지막 계단의 최댓값 2가지 중, 더 큰 값을 출력한다.

 

 

---

입력 예제

 

6
10
20
15
25
10
20

 

 

 

출력 예제

 

75

 

---

주의할 점

 

연속 3개의 계단을 오르면 안된다라는 제약 조건을 잘 캐치하여 문제를 접근해야 한다.

 

---

전체 코드

 

# 2579

import sys
input = sys.stdin.readline

def solution():
    dp = []

    # dp 각 요소의 0번째 인덱스 : 현재 계단을 연속 1개 째 밟은 상태
    # dp 각 요소의 1번째 인덱스 : 현재 계단을 연속 2개 째 밟은 상태
    
    # dp[0] : 시작점
    dp.append([0, 0])

    # dp[1] : 첫 번째 계단
    dp.append([stair[1], 0])

    for idx in range(2, n+1):
        dp.append([])
        # 0번째 인덱스 : 현재 계단을 연속 1개 째 밟은 상태 = 계단을 2개 뛰어 넘은 상태의 최댓값
        dp[idx].append(max(dp[idx - 2]) + stair[idx])

        # 1번째 인덱스 : 현재 계단을 연속 2개 째 밟은 상태 = 이전 게단의 최댓값 중, 계단 1개를 연속으로 밟은 값에서만 따져야 함
        dp[idx].append(dp[idx - 1][0] + stair[idx])
    
    print(max(dp[-1]))

if __name__ == "__main__":
    n = int(input())

    stair = [0] # 0번째 인덱스는 더미 값
    for _ in range(n):
        stair.append(int(input()))
    
    solution()

 

---

풀이 후기

 

다이나믹 프로그래밍 문제는 많이 풀어보며 경험을 쌓아야 하는 문제이니 만큼, 꾸준히 풀어야겠다고 생각했다.

오랜만에 문제를 풀어보니 점화식을 유도하는 과정에서 시간이 상당히 많이 걸리고 머리도 아팠다..