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

📌 문제 탐색하기

N : N개의 줄

matrix : N x 3 2차원 배열

 

숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나이며 N개의 행에 걸쳐 세 개의 숫자가 주어집니다.

각 행에서 한 숫자를 선택하며 아래로 내려가면서 숫자들의 합을 구하는 게임입니다.
목표는 제시된 이동 규칙에 따라 내려오면서 얻을 수 있는 최대 점수와 최소 점수를 구하는 것입니다.

가능한 시간복잡도

1. 조합
   
   • 각 행마다 최악의 경우 약 3가지의 선택지가 있을 수 있습니다.
     • 첫 번째 열이나 마지막 열에서는 선택지가 2가지이지만, 최악의 경우(즉, 항상 3가지 선택이 가능한 경우)를 가정합니다.
   • 첫 행에서 3가지 선택이 있고, 그 다음부터는 각 행마다 최대 3가지 선택이 있습니다.
     • 전체 경로의 개수는 3 × 3^(N-1)입니다.
   • O(3^N)의 시간복잡도를 가지게 되어 N이 커지면 실행 시간이 기하급수적으로 늘어나게 됩니다.
2. DP ( 동적계획법 ) 
   
   • 첫 행에서 시작할 때는 3개 숫자 중 원하는 숫자를 선택합니다.
   • 이후 행으로 내려갈 때, 현재 위치의 바로 아래, 혹은 바로 아래의 왼쪽 또는 오른쪽에 있는 숫자로만 이동할 수 있습니다.
     • 열이 0이면 다음 행에서 이동 가능한 열은 0과 1 입니다.
     • 열이 1이면 이동 가능한 열은 0, 1, 2 입니다.
     • 열이 2이면 이동 가능한 열은 1과 2입니다.
   • DP는 각 행마다 가능한 3가지 상태(각 열의 값)를 기록하면서 이전 행의 결과만 이용하여 현재 행의 결과를 계산합니다.
   • 매번 이전 집의 상태(3가지)만을 기억하여 한 번만 계산하면 되기 때문에 시간복잡도가 O(N)입니다.

알고리즘 선택

각 행마다 각 위치에서 도달 가능한 최대 점수와 최소 점수를 저장하고,
다음 행으로 내려갈 때 이전 행의 결과를 이용해 갱신하는 방식인 DP(동적계획법)를 사용하여 접근해 보겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. 최대 점수와 최소 점수를 저장하는 3 * N인 2차원 배열을 만듭니다.
   1. maxDP[i][j]: i번째 행의 j번째 열까지 내려오면서 얻을 수 있는 최대 점수
   2. minDP[i][j]: i번째 행의 j번째 열까지 내려오면서 얻을 수 있는 최소 점수
3. 점화식 수행:
   1.  최대값 갱신
      1. 첫번째 열 : maxDP[i][0] = matrix[i][0] + max(maxDP[i-1][0], maxDP[i-1][1])
      2. 두번째 열 : maxDP[i][1] = matrix[i][1] + max(maxDP[i-1][0], maxDP[i-1][1], maxDP[i-1][2])
      3. 세번째 열 : maxDP[i][2] = matrix[i][2] + max(maxDP[i-1][1], maxDP[i-1][2])
   2. 최솟값 갱신
      1. 첫번째 열 : minDP[i][0] = matrix[i][0] + min(minDP[i-1][0], minDP[i-1][1])
      2. 두번째 열 : minDP[i][1] = matrix[i][1] + min(minDP[i-1][0], minDP[i-1][1], minDP[i-1][2])
      3. 세번째 열 : minDP[i][2] = matrix[i][2] + min(minDP[i-1][1], minDP[i-1][2])
4. 결과 출력: 마지막 행의 maxDP에서 최대값과, minDP에서 최소값을 출력하면 됩니다.

---

📌 시도 회차 수정 사항 (Optional)

• 메모리 초과 발생
  • 설계한 코드대로 maxDP와 minDP 배열을 각각 N행 × 3열 크기로 생성했습니다
    • maxDP 또는 minDP는 각각 N × 3 크기입니다.
    • N = 100,000이면, 각 배열에는 100,000 × 3 = 300,000개의 요소가 있습니다.
  • 메모리 오버헤드가 발생합니다.
    • Python에서 정수 하나는 보통 최소 28바이트의 메모리를 차지합니다.
    • 300,000개의 정수는 300,000 × 28 = 8,400,000 바이트, 즉 약 8.4MB 정도가 필요합니다.
    • maxDP와 minDP, 두 배열 모두 만들어야 하므로 총 메모리 사용량은 8.4MB × 2 = 16.8MB  객체 메모리가 필요합니다.
    • 입력 행렬도 별도로 저장하기 때문에 같은 크기(300,000개의 정수)를 가지므로 추가적인 8.4MB 정도가 필요합니다.
  • 설계를 수정합니다.
    • DP 배열 크기 줄이기
      • maxDP와 minDP에 현재 행과 바로 이전 행만 저장합니다.
      • 길이가 3인 두개의 리스트만 사용하므로, 총 6개의 정수만 저장하게 됩니다.
      • 입력 행렬도 한 행씩 입력을 받아 처리하여 메모리 부담을 줄입니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
first_row = list(map(int, input().split()))

maxDP = [first_row[:], [0] * 3]
minDP = [first_row[:], [0] * 3]

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

print(max(maxDP[0]), min(minDP[0]))