[알고리즘] 백준 파이썬 2096 내려가기

 

📍 문제 탐색하기

내려가기 성공 문제는 N줄에 0 이상 9 이하의 숫자가 세 개씩 주어진 배열에서 첫 줄에서 시작해 마지막 줄까지 내려가며 얻을 수 있는 최대 점수와 최소 점수를 구하는 문제다.

• 현재 위치에서 바로 아래의 숫자 또는 인접한 숫자로만 이동할 수 있다.
• 점수는 이동한 위치의 숫자의 합으로 계산된다.

입력 범위

• N: 1 ≤ N ≤ 100,000
• 각 줄에 주어진 숫자: 0 ~ 9
• 시간과 메모리 제약을 고려해야 한다.

가능한 시간복잡도

최대 N=100,000에서, 각 줄마다 최대 3개의 숫자를 탐색하므로, O(N) 시간 복잡도로 해결해야 한다.
이를 위해 동적 계획법(DP)을 사용해 각 위치에서 얻을 수 있는 최대 및 최소 점수를 효율적으로 계산한다.

알고리즘 선택

• 동적 계획법(DP)을 사용한다.
• 한 줄의 숫자만 메모리에 유지하면서 다음 줄로 진행하므로 메모리 사용을 최소화한다.
• 각 줄의 최대/최소 점수를 DP로 계산해, 메모리 초과를 방지하고 효율성을 높인다.

---

📍 코드 설계하기

• 문제의 Input을 받는다.
• N을 입력받고, 각 줄에 적힌 세 개의 숫자를 배열로 정의한다.
• 동적 계획법(DP)을 이용해 현재 행의 최대/최소 점수를 계산한다.
• 이전 행의 결과를 기준으로, 현재 위치에서 가능한 이동(왼쪽 대각선, 바로 위, 오른쪽 대각선)을 고려한다.
• 마지막 줄의 최대 점수와 최소 점수를 출력한다.

---

📍 시도 회차 및 수정 사항

1차 시도 (메모리 초과) ❌

import sys
import copy
input = sys.stdin.readline

N = int(input())

max_dp = [list(map(int,input().split())) for _ in range(N)]
min_dp = copy.deepcopy(max_dp)

for i in range(1, N):
    max_dp[i][0] = max_dp[i][0] + max(max_dp[i-1][0], max_dp[i-1][1])
    min_dp[i][0] = min_dp[i][0] + min(min_dp[i-1][0], min_dp[i-1][1])
    
    max_dp[i][1] = max_dp[i][1] + max(max_dp[i-1][0], max_dp[i-1][1], max_dp[i-1][2])
    min_dp[i][1] = min_dp[i][1] + min(min_dp[i-1][0], min_dp[i-1][1], min_dp[i-1][2])
    
    max_dp[i][2] = max_dp[i][2] + max(max_dp[i-1][1], max_dp[i-1][2])
    min_dp[i][2] = min_dp[i][2] + min(min_dp[i-1][1], min_dp[i-1][2])
    
print(' '.join(map(str, [max(max_dp[N-1]), min(min_dp[N-1])])))

문제점

• 모든 줄을 메모리에 저장하여 메모리 초과 발생.
• 특히 N=100,000일 경우, 행렬 크기가 지나치게 커진다.

---

2차 시도 (메모리 최적화) ✅

import sys
input = sys.stdin.readline

N = int(input())

prev_max_dp = list(map(int, input().split()))
prev_min_dp = prev_max_dp[:]

for i in range(1, N):
    cnt = list(map(int, input().split()))
    
    # 현재 행의 최댓값
    cnt_max_dp = [
        cnt[0] + max(prev_max_dp[0], prev_max_dp[1]),
        cnt[1] + max(prev_max_dp[0], prev_max_dp[1], prev_max_dp[2]),
        cnt[2] + max(prev_max_dp[1], prev_max_dp[2])
    ]
    
    # 현재 행의 최솟값
    cnt_min_dp = [
        cnt[0] + min(prev_min_dp[0], prev_min_dp[1]),
        cnt[1] + min(prev_min_dp[0], prev_min_dp[1], prev_min_dp[2]),
        cnt[2] + min(prev_min_dp[1], prev_min_dp[2])
    ]
    
    prev_max_dp = cnt_max_dp
    prev_min_dp = cnt_min_dp
    
print(' '.join(map(str, [max(prev_max_dp), min(prev_min_dp)])))

해결 방법

• 한 줄의 DP 결과만 유지하면서 이전 줄의 DP 결과를 기반으로 다음 줄 계산한다.
• O(1) 추가 메모리만 사용해 효율적으로 문제를 해결해주었다.
• 메모리 초과 없이, O(N) 시간 복잡도로 해결 가능하다!

 

---

📍 느낀점

1. 메모리 최적화의 중요성을 느꼈다. 모든 데이터를 저장하는 방식은 제한된 환경에서 문제가 생길 수 있음을 알게 됐다.
2. DP를 이용한 문제 해결에서 공간 복잡도를 줄이는 방법을 배우는 계기가 되었다.
3. 최종적으로 효율적인 메모리 사용과 간결한 구현으로 최적화할 수 있어 의미 있었다!