1️⃣ 서론
이 문제는 백준 2096 내려가기 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다.
2️⃣ 문제 설명
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. 첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력하는 문제이다.
3️⃣ 풀이
예전에 비슷한 문제를 푼 적이 있어서 dp라는 것을 쉽게 유추할 수 있었다. 하지만 여기서 중요한 것은 메모리가 4MB로 제한 된다는 점이다. 이 때문에 배열을 불필요하게 많이 사용할 수 없어서 코드를 고치느라 조금 애를 먹었다. 아래는 메모리 초과를 일으킨 코드이다.
메모리 초과를 일으킨 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
arr.append(list(map(int, input().split())))
max_dp = [[0] * 3 for _ in range(n)]
min_dp = [[0] * 3 for _ in range(n)]
for i in range(3):
max_dp[0][i] = arr[0][i]
min_dp[0][i] = arr[0][i]
for i in range(1, n):
for j in range(3):
if j == 0:
max_dp[i][j] = arr[i][j] + max(max_dp[i - 1][j], max_dp[i - 1][j + 1])
min_dp[i][j] = arr[i][j] + min(min_dp[i - 1][j], min_dp[i - 1][j + 1])
elif j == 1:
max_dp[i][j] = arr[i][j] + max(max_dp[i - 1][j - 1], max_dp[i - 1][j], max_dp[i - 1][j + 1])
min_dp[i][j] = arr[i][j] + min(min_dp[i - 1][j - 1], min_dp[i - 1][j], min_dp[i - 1][j + 1])
else:
max_dp[i][j] = arr[i][j] + max(max_dp[i - 1][j], max_dp[i - 1][j - 1])
min_dp[i][j] = arr[i][j] + min(min_dp[i - 1][j], min_dp[i - 1][j - 1])
print(max(max_dp[n - 1]), min(min_dp[n - 1]))
이를 해결하기 위해선 배열 arr와 max_dp, min_dp 배열까지 선언을 하지않고 하나의 변수에 기억하는 방법을 사용해야 했다. 이를 해결한 코드는 다음과 같다.
4️⃣ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
input = sys.stdin.readline
n = int(input())
max_dp = [0] * 3
min_dp = [0] * 3
max_tmp = [0] * 3
min_tmp = [0] * 3
for i in range(n):
a, b, c = map(int, input().split())
for j in range(3):
if j == 0:
max_tmp[j] = a + max(max_dp[j], max_dp[j + 1])
min_tmp[j] = a + min(min_dp[j], min_dp[j + 1])
elif j == 1:
max_tmp[j] = b + max(max_dp[j - 1], max_dp[j], max_dp[j + 1])
min_tmp[j] = b + min(min_dp[j - 1], min_dp[j], min_dp[j + 1])
else:
max_tmp[j] = c + max(max_dp[j], max_dp[j - 1])
min_tmp[j] = c + min(min_dp[j], min_dp[j - 1])
for j in range(3):
max_dp[j] = max_tmp[j]
min_dp[j] = min_tmp[j]
print(max(max_dp), min(min_dp))
5️⃣ 마치며
전형적인 dp 문제여서 그렇게 어려운 문제는 아니었지만 메모리를 고려해 dp의 공간을 고려해야 하는 문제였다. 이를 주의해야 한다.
