백준: 2579 계단 오르기

문제

2579번: 계단 오르기

 

문제 풀이

 계단 아래 시작점부터 꼭대기에 위치한 도착점까지 도착하고자 한다. 각 계단에는 획득할 수 있는 점수가 있으며, 계단을 밟을 수 있는 규칙이 존재한다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안된다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 따라서 이 문제는 경우의 수를 뻗어 가능한 경우 중 가장 큰 수를 찾는 문제와 같다. 계단의 개수가 300개 이하이므로 `DFS`로 풀게 될 경우 당연히 시간 초과가 발생한다. 따라서 `DP`로 풀어야 한다. `DP`로 문제를 풀기 위해서는 다음과 같이 문제를 접근하면 된다.

 

• 초기에 활용할 DP 값을 다음과 같이 초기화한다.
  • `DP[0] = 첫 번째 계단`
  • `DP[1] = 첫 번째 계단 + 두 번째 계단`
  • `DP[2] = max(첫 번째 계단 + 세 번째 계단, 첫 번째 계단 + 두 번째 계단)`
• 이후 DP[3] 부터는 점화식을 통해 값을 계산할 수 있다.
  • `DP[N] = 현재 계단 + max(전 계단 + 전전전 계단, 전전 계단)`
• 최대 3칸을 연속해서 밟을 수 없어, 현재 칸을 기준으로 위와 같은 점화식을 통해 답을 찾을 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    n = int(stdin.readline())
    stair = [int(stdin.readline()) for _ in range(n)]

    # 3보다 작은 경우, 아래 로직은 인덱스 오류 발생
    if n < 3:
        print(sum(stair))
        exit(0)

    dp = [0] * n

    #  dp[0], dp[1], dp[2] 초기화
    dp[0], dp[1] = stair[0], sum(stair[:2])
    dp[2] = max(stair[1] + stair[2], stair[0] + stair[2])

    for i in range(3, n):
        '''
        연속해서 밟을 수 없으므로
        1. 현재 계단 + 전 계단 + 전전전 계단
        2. 현재 계단 + 전전 계단
        '''
        dp[i] = stair[i] + max(stair[i - 1] + dp[i - 3], dp[i - 2])

    print(dp[-1])