이번 글에서 다룰 문제는 총 3개다.
백준 2579. 계단 오르기
https://www.acmicpc.net/problem/2579
백준 9095. 1, 2, 3 더하기
https://www.acmicpc.net/problem/9095
백준 11726. 2xn 타일링
https://www.acmicpc.net/problem/11726
세 문제 다 솔브닥 기준 실버 3, 그리고 Class 3에서 가져온 문제들이라서 객관적으로는 그리 어려운 문제가 아니다.
하지만 그리디, 탐색(dfs, bfs)에 비해 훨씬 생소한 다이나믹 프로그래밍인데다가,
점화식이 바로 떠오르는 피보나치 수열 문제도 아니라서 뭐 어떻게 풀어야 하는지 막막할 때가 많았다.
문제를 하나하나씩 살펴보면서 문제의 뉘앙스, 그리고 세 문제에 공통적으로 적용되는 풀이 방식을 익혀보도록 하자.
2579. 계단 오르기
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다. - 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
예제 입력 1
6
10
20
15
25
10
20예제 출력 1
75풀이
풀이를 성급히 보지 말고, 한번 스스로 생각해보자.
필자의 경우 생각할 수록 케이스를 어떻게 나눠야 할지 막막했고,
카테고리가 다이나믹 프로그래밍이라는 사실을 알았음에도 어떻게 코드를 짜야 할지 선뜻 생각이 나지 않았다.
import sys
n = int(sys.stdin.readline().rstrip())
dp = [0] * n
stairs = []
for _ in range(n):
stairs.append(int(sys.stdin.readline().rstrip()))
dp[0] = stairs[0]
if n == 1:
print(dp[0])
exit()
dp[1] = stairs[0] + stairs[1]
if n == 2:
print(dp[1])
exit()
dp[2] = max(stairs[1] + stairs[2], stairs[0] + stairs[2])
for i in range(3, n):
dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])
print(dp[n-1])연속 세개의 계단을 올라가는 것은 불가능하므로, 역으로 생각해보면 케이스는 두 개밖에 없다.
- 지금 계단, 바로 직전 계단을 사용하고, 한 칸 띄고 3번째 전 계단을 이용하는 케이스.
- 지금 계단, 한 칸 띄어 2번째 전 계단을 이용한 뒤, 그 직전인 3번째 전 계단을 이용한 케이스.
아니다. 사실 두 개가 아니다.
- 지금 계단, 한 칸 띄어 2번째 전 계단을 이용한 뒤, 거기서 또 한 칸 띄어 4번째 전 계단을 이용하는 것도 가능하다.
아니, 그리고 3번째 전 계단을 이용하는 케이스, 4번째 전 계단을 이용하는 케이스 역시 재귀적으로 계속 그 전 계단 어디를 갈 건지도 정해야 하는 것 아닌가?
dp[k]가 stairs[k]를 도착으로 하는 경우의 수 중 최대 점수를 담고 있다고 가정하자.
그렇다면, dp[k]는 두 가지 경우의 수로 나눌 수 있다.
stairs[k]+stairs[k-1]+dp[i-3]stairs[k]+dp[i-2]
정말 깔끔하지 않은가?
그래서 다음의 점화식을 이용하여 상향식 다이나믹 프로그래밍(타뷸레이션Tabulation 이라고 함)을 구성할 수 있다.
for i in range(3, n):
dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])9095. 1, 2, 3 더하기
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
예제 입력 1
3
4
7
10예제 출력 1
7
44
274풀이
import sys
dp = [0] * 11
dp[1] = 1 # 1
dp[2] = 2 # 1+1, 2
dp[3] = 4 # 1+2, 2+1, 1+1+1, 3
for i in range(4, 11):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
T = int(sys.stdin.readline().rstrip())
for _ in range(T):
n = int(sys.stdin.readline().rstrip())
print(dp[n]) 이건 위의 문제보다 점화식을 생각하기 더 어렵다.
이럴 때는 진짜 수학적으로 떠올려보는 것보다, dp[1]부터 차근차근 해보면서 대충 어떤 규칙성이 있겠거니 수열의 규칙을 찾는 것이 초보자로서 훨씬 유리하다.
여기서 dp[1] = 1, dp[2] = 2, dp[3] = 4, dp[4] = 7, dp[5] = 13
어떤 규칙성이 보이는가?
for i in range(4, 11):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]11726. 2xn 타일링
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
2예제 출력 1
2예제 입력 2
9예제 출력 2
55풀이
import sys
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
n = int(sys.stdin.readline().rstrip())
for i in range(5, 1001):
dp[i] = dp[i-2] + dp[i-1]
print(dp[n] % 10007)얘도 위 문제와 마찬가지다. 수학적으로 다 생각해보기가 너무 어려우니까... 적은 숫자들로 수열의 규칙성을 파악하는 것이다.
dp[1] = 1, dp[2] = 2, dp[3] = 3, dp[4] = 5, dp[5] = 8
와! 피보나치 수열이다. 왜지?
어쨌든 점화식은 다음과 같다.
for i in range(5, 1001):
dp[i] = dp[i-2] + dp[i-1]dp 초기값 넣을 때의 주의사항
dp 배열 크기를 [0] * 1001 처럼 다 만들어 놀거냐,
아니면 입력된 n 크기만큼만 만들거냐는 자유지만,
n 크기만큼만 만들면 dp[1], dp[2]과 같은 초기값을 주는 과정에서 IndexError가 날 수 있으니 주의해야 한다.
한 마디로, n = 1이면 어쩔려고?
dp = [0] * n
dp[0] = stairs[0]
if n == 1:
print(dp[0])
exit()
dp[1] = stairs[0] + stairs[1]
if n == 2:
print(dp[1])
exit()위 방식대로 하거나, 그게 아니라면
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5이 방식대로 해야 된다.
마치며
아직 우리는 플래티넘 문제를 풀고 있는게 아니지 않은가?
그렇게 어려운 경우의 수를 다 계산하라고는 하지 않는다.
dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
dp[i] = dp[i-2] + dp[i-1]
이번 세 문제는, 다이나믹 프로그래밍 중에서도 재귀를 사용하지 않는 상향식(타뷸레이션 방식)을 사용해보았다.
상향식 다이나믹 프로그래밍(타뷸레이션)과 하향식 다이나믹 프로그래밍(메모이제이션)의 차이에 대해서는 이 링크를 참고해주세요.
이정도의 점화식을 찾아낼 줄만 안다면 상향식 다이나믹 프로그래밍은 끄떡 없다.
