[백준] 2579번 계단 오르기(feat. 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/2579

 

문제 분석

• 첫 번째 단계 (문제 요약 및 조건 파악하기)

시작점에서 출발하여 마지막 도착 계단까지 가는 경로 중에, 가중치가 가장 큰 경로를 찾아서 해당 가중치를 반환해야 하는 문제이다.

규칙으로는
한 번에 한 계단 또는 두 계단 씩 오를 수 있고,
연속된 세 개의 계단을 모두 밟을 수는 없다.(시작점은 포함 X)
마지막 도착 계단은 무조건 밟아야 한다.

입력으로 주어지는 계단의 개수는 300이하의 자연수,
계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

• 두 번째 단계 (문제의 핵심 파악하기)

우리는 어찌되었건, n번째 계단에 올라야 한다.
그렇다면, n번째 계단에 오르는 경우의 수를 생각해보자. 총 4가지로 생각할 수 있다.

1. 한 계단 or 두 계단 올라서 n - 1 번째 계단에 도착한 후 한 계단 오르기(총 2가지)
2. 한 계단 or 두 계단 올라서 n - 2 번째 계단에 도착한 후 두 계단 오르기(총 2가지)
그러나, 문제에서 주어진 "연속 3계단을 오를 수 없다"라는 조건을 고려하면, "한 계단 올라서 n - 1계단에 도착한 후, 한 계단 오르기"의 경우는 탈락된다. 
총 3가지 경우가 남는다.

 

문제를 잘 생각해보자.
한 계단 or 두 계단을 오르는 각 과정을 수행하는 것을 "단계"라고 표현하면,
현재 x단계를 수행할 때는, x - 1단계 or x - 2 단계가 영향을 미친다.

즉, 1. 큰 문제를 작은 문제로 나눌 수 있다.(최적 부분 구조)
n번째 계단에 도달해야 하는데, 그것의과정을 |
1. 한 계단 or 두 계단 올라서 n - 1 번째 계단에 도착한 후 한 계단 오르기(총 2가지)
2. 한 계단 or 두 계단 올라서 n - 2 번째 계단에 도착한 후 두 계단 오르기(총 2가지)
그러나, 문제에서 주어진 "연속 3계단을 오를 수 없다"라는 조건을 고려하면, "한 계단 올라서 n - 1계단에 도착한 후, 한 계단 오르기"의 경우는 탈락된다. 

이렇게 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.(중복되는 부분 문제)
앞서 계단을 오르는 과정이 이후 계단을 오르는 과정에 영향을 미친다.

따라서, 이 문제는 다이나믹 프로그래밍으로 풀이를 진행할 수 있다.

 

 

 

 

DP테이블을 정의 해보자.

 

DP테이블을 2차원 배열로 정의할 수 있을 것이다.

 

• dp[i][0] = 한 계단 올라서 i 번째 계단에 도착한 경우
• dp[i][0] = 두 계단 올라서 i 번째 계단에 도착한 경우

점화식을 세워보자. 입력 받은 계단별 가중치를 저장한 배열을 stair[]이라고 가정한다.

앞서 문제에서 주어진 "연속 3계단을 오를 수 없다"라는 조건을 고려하면, "한 계단 올라서 n - 1계단에 도착한 후, 한 계단 오르기"의 경우는 탈락되었으므로, 

• dp[i][0] = dp[i - 1][1] + stair[i]  # 한 계단 올라서 도착점에 도달 하려면, 이전에는 한 번에 두 계단을 올라온 상태여야 한다.
• dp[i][1] = max(dp[i - 2]) + stair[i] # 두 계단 올라서 도착점에 도달 하려면, 이전에는 한 계단 or 두 계단 올라온 상태 아무거나 ok(둘 중 큰 값이면 된다.)

'''
시작점에서 출발하여 마지막 도착 계단까지 가는 경로 중에, 가중치가 가장 큰 경로를 찾아서 해당 가중치를 반환해야한다.

규칙으로는,
한번에 한계단 또는 두 계단씩 오를 수 있고,
연속된 세 개의 계단을 모두 밟아서는 안된다.(시작점은 포함X)
마지막 도착 계단은 무조건 밟아야 한다.

i)
n 번째 계단을 오르기 위해서는, 모두 4가지 경우의 수가 있다고 가정할 수 있다.
1. 한 계단 or 두 계단 올라서 n - 1 번째 계단에 도착한 후 한 계단 오르기 (총 2가지)
2. 한 계단 or 두 계단 올라서 n - 2 번째 계단에 도착한 후 두 계단 오르기 (총 2가지)
그러나, 여기서 문제에서 주어진 연속 3계단을 오를 수 없다는 조건에 의해, "한 계단 올라서 n - 1계단에 도착한 후, 한 계단 오르기"의 경우는 탈락
총 3가지 경우가 남는다.

dp[i][0] = 한 계단 올라서 i번째 계단에 도착한 경우
dp[i][1] = 두 계단 올라서 i 번째 계단에 도착한 경우

구현해보자.
'''

 

코드 작성

import sys

n = int(sys.stdin.readline().rstrip())

stair = []
for i in range(n):
    w = int(sys.stdin.readline().rstrip())
    stair.append(w)
stair.insert(0, 0)
# print(stair)

dp = [[0, 0] for _ in range(n + 2)]

for i in range(n + 1):
    dp[i][0] = dp[i - 1][1] + stair[i]
    # print(dp)
    dp[i][1] = max(dp[i - 2]) + stair[i]
    # print(dp)

print(max(dp[n]))

 

주의할 것이 있다.

만약 dp 테이블의 길이를 n + 1로 선언해주면,
n이 1일 때,
dp[i][1]이 갱신하는 과정에서, dp[i][0]에서 갱신한 값을 사용하는 문제가 발생한다.

'''
예를 들어 입력이
1
20 이라면,
길이가 n + 1인 dp테이블을 선언 한다면,

i = 0
dp[0][0] = dp[0 - 1][1] + stair[0] = 0 -> [[0, 0], [0, 0]]
dp[0][1] = max(dp[0 - 2]) + stair[0] = 0 -> [[0, 0], [0, 0]]

i = 1
dp[1][0] = dp[1 - 1][1] + stair[1] = 20 -> [[0, 0], [20, 0]]
dp[1][1] = max(dp[1 - 2]) + stair[1] = 20 + 20 = 40 -> [[0, 0], [20, 40]]

------------------------------------------------------------------------
따라서 이러한 문제를 방지하기 위해,

dp 테이블의 길이를 n + 2로 선언 해주어야 한다.

i = 0
dp[0][0] = dp[0 - 1][1] + stair[0] = 0 -> [[0, 0], [0, 0], [0, 0]]
dp[0][1] = max(dp[0 - 2]) + stair[0] = 0 -> [[0, 0], [0, 0], [0, 0]]

i = 1
dp[1][0] = dp[1 - 1][1] + stair[1] = 20 -> [[0, 0], [20, 0], [0, 0]]
dp[1][1] = max(dp[1 - 2]) + stair[1] = 20 -> [[0, 0], [20, 20], [0, 0]]

이렇게 문제가 없게된다.
'''

이러한 문제는 DP 유형을 풀다보면, 많이 접할 것이다.
주의사항을 기억해 놓도록 하자.