[백준/파이썬] 2579 계단 오르기 - 다이나믹 프로그래밍

➰ 2579번 계단 오르기

---

💡 구현 아이디어

---

이 문제는 다이나믹 프로그래밍으로 풀이했는데, 먼저 다이나믹 프로그래밍에 대해 알아보겠다.

 

1. 다이나믹 프로그래밍이란

다이나믹 프로그래밍은 메모리를 잘 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

 

2. 다이나믹 프로그래밍 구현 방법

다이나믹 프로그래밍 구현 방법은 크게 두 가지가 있다.

1) Top-Down, 하향식 방식

큰 문제를 해결하기 위해 작은 문제를 호출하는 방법으로 재귀 함수를 이용하여 코드를 작성한다. 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 메모이제이션(Memoization) 방식이라고도 하며 재귀함수를 이용한다.

정확히 말하면 메모이제이션은 이전에 계산된 결과를 캐싱해 놓는 것이기 때문에 DP에만 국한된 개념은 아니다.

2) Bottom-Up, 상향식 방식

작은 문제부터 차근차근 답을 도출하는 방법으로 반복을 이용하여 코드를 작성한다. 상향식 방식에서 사용되는 결과 저장용 테이블은 'DP 테이블'이라고 부른다. 상향식 방식은 반복문을 이용해 구현한다.

책 <이것이 취업을 위한 코딩 테스트다>를 보면 DP에서 가능하다면 재귀 함수를 이용하는 하향식 방식보다는 Bottom-Up 방식으로 구현하는 것을 권장한다고 나와 있다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

 

3. 다이나믹 프로그래밍의 조건

다이나믹 프로그래밍은 보통 문제가 다음 두 조건을 만족할 때 사용한다.

 

1) 최적 부분 구조, Optimal Substructure

큰 문제를 작은 문제로 나눌 수 있다.

 

2) 중복되는 부분 문제, Overlapping Subproblem

동일한 작은 문제를 반복적으로 해결해야 한다.

 

말이 추상적이라 잘 와닿지 않을 수 있는데, 문제가 점화식으로 표현 가능하고, 시간 제한이 빡센 문제인 경우 보통 DP로 풀이한다.

 

4. 다이나믹 프로그래밍 행동영역 (Bottom-Up)

주어진 문제가 DP 유형임을 파악하는 것이 중요하다. 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한다. 다른 알고리즘 풀이가 떠오르지 않거나, 시간초과가 해결되지 않을 때 DP를 고려하는 것이 좋다.

 

1) 문제를 보고 DP로 풀어야겠다고 판단

2) DP 테이블 세팅 및 초기화

3) 점화식 표현

4) 반복문 사용해서 DP 테이블 업데이트

 

💻 계단 오르기 DP 풀이

---

위에서 정리한 DP 행동영역에 따라 풀이해보도록 하겠다.

 

1. DP 유형 파악

 

2. DP 테이블 세팅

DP 값은 해당 계단에서 얻을 수 있는 총 점수의 최댓값이다.

 

3. 점화식 표현

이제 문제에서 요구하는 내용을 점화식으로 표현해야 한다. 바로 떠오르지는 않으니 예제를 먼저 관찰하도록 하겠다.

문제에 나오는 예제를 보자. 마지막 계단은 항상 포함되어야 하고, 세 개의 계단이 연속으로 선택되면 안 된다. 인덱스 N, 즉 마지막 계단 기준 N-1 계단은 선택될 수도 있고, 안 될 수도 있다. 따라서 점수 합이 최대가 되는 케이스는 N-1번째 계단의 선택 여부에 따라 다음 두 가지가 있다.

 

 

각각의 경우를 점화식으로 표현하면 다음과 같다. 다음 가능한 두 가지 경우를 비교하여 더 큰 값을 선택하면 된다.

 

CASE1 = dp[N-2] + sc[N]
CASE2 = dp[N-3] + sc[N-1] + sc[N]

 

4. 반복문 사용해서 DP 테이블 업데이트

이제 반복문을 돌면서 DP 테이블을 업데이트 해준다. 점화식의 인덱스를 맞추기 위해 DP 테이블을 초기화해주었다.

 

전체 소스코드

N = int(input())
sc = [int(input()) for _ in range(N)]
dp = [0] * N

if N < 2:
    dp[N-1] = sum(sc)
else:
    dp[0] = sc[0]
    dp[1] = dp[0] + sc[1]

for i in range(2, N):
    dp[i] = max(dp[i-2], dp[i-3] + sc[i-1]) + sc[i]

print(dp[N-1])