[백준 / Python] 2096 내려가기

Posted by Kyun2da on April 27, 2021

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의 공간을 고려해야 하는 문제였다. 이를 주의해야 한다.