[백준] #2096 내려가기(python)

📌문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

예제 입력1

3
1 2 3
4 5 6
4 9 0

예제 출력1

18 6

예제 입력2

3
0 0 0
0 0 0
0 0 0

예제 출력2

0 0

백준 2096번 문제

💡Idea

이 문제는 메모리를 상당히 신경쓰며 풀어야 하는 문제입니다.

그래서 메모리를 줄이기 위하여 굉장히 다양한 시도 끝에 풀었던 문제입니다🤪

처음에는 DFS를 이용하여 문제를 해결하고자 했습니다.

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
possible_pos = [[0, 1], [0, 1, 2], [1, 2]]
ans_set = set()

def dfs(i, j, score):
    if i >= (N - 1): ans_set.add(score)
    else:
        for pos in possible_pos[j]:
            dfs(i + 1, pos, score + arr[i + 1][pos])

for i in range(3):
    dfs(0, i, arr[0][i])
    
print(max(ans_set), min(ans_set))

하지만, DFS는 메모리 초과가 발생합니다.

그 다음에는, ans_set의 메모리를 줄이기 위하여 그리디하게 문제를 풀어보았습니다. 하지만 그리디로는 제대로 된 정답을 찾을 수 없습니다.

결국, DP로 문제를 해결할 수 있었습니다.

• 첫 번째 칸은 이전의 첫 번째 칸과 두 번째 칸으로부터 올 수 있습니다.
• 두 번째 칸은 이전의 어느 칸으로부터든 올 수 있습니다.
• 세 번째 칸은 이전의 두 번째 칸과 세 번째 칸으로부터 올 수 있습니다.

이를 바탕으로 한 줄씩 입력을 받을 때마다 각 칸 별로 가질 수 있는 가장 큰 값과 가장 작은 값을 저장한 뒤 마지막 세 칸 중 가장 큰 값과 가장 작은 값을 답으로 찾으면 됩니다.

• 첫 번째 칸은 이전의 첫 번째 칸 + 현재 칸과 이전의 두 번째 칸 + 현재 칸 중 더 큰 값(최솟값을 찾을 때는 더 작은 값)을 가지게 됩니다.
• 두 번째 칸은 이전의 첫 번째 칸 + 현재 칸과 이전의 두 번째 칸 + 현재 칸, 이전의 세 번째 칸 + 현재 칸 중 더 큰 값(최솟값을 찾을 때는 더 작은 값)을 가지게 됩니다.
• 세 번째 칸은 이전의 두 번째 칸 + 현재 칸과 이전의 세 번째 칸 + 현재 칸 중 더 큰 값(최솟값을 찾을 때는 더 작은 값)을 가지게 됩니다.

📍 이 때 주의할 점은, 입력도 한 번에 받아 저장하면 안되고 한 줄씩 받고 이전 입력은 버려야 한다는 점입니다.

💻코드

• ⏰ 시간 : 312 ms / 메모리 : 30748 KB

import sys
input = sys.stdin.readline
N = int(input())
dp = [list(map(int, input().split()))] * 2

for i in range(1, N):
    nums = list(map(int, input().split()))
    dp[0] = [nums[0] + max(dp[0][0], dp[0][1]), nums[1] + max(dp[0]), nums[2] + max(dp[0][1], dp[0][2])]
    dp[1] = [nums[0] + min(dp[1][0], dp[1][1]), nums[1] + min(dp[1]), nums[2] + min(dp[1][1], dp[1][2])]

print(max(dp[0]), min(dp[1]))

📝코드 설명

변수

• dp : 각 줄을 입력받을 때마다, 그 때까지의 각 칸의 최댓값과 최솟값을 저장하는 리스트
  dp[0]에는 최댓값이, dp[1]에는 최솟값이 저장된다.

맨 처음 dp에는 첫 번째 줄의 값들이 저장됩니다.

그리고 나머지 N-1번의 입력을 받으며, 그 때까지의 각 칸이 가질 수 있는 가장 큰 값과 가장 작은 값을 각각 dp[0]과 dp[1]에 저장해주면 됩니다.

마지막에 남은 dp[0] 중 가장 큰 값이 최댓값, dp[1]중 가장 작은 값이 최솟값이 됩니다.