알고리즘
[알고리즘] 백준 파이썬 2096 내려가기
chaewonni
2025. 1. 13. 23:58
📍 문제 탐색하기
내려가기 성공 문제는 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) 시간 복잡도로 해결 가능하다!
📍 느낀점
- 메모리 최적화의 중요성을 느꼈다. 모든 데이터를 저장하는 방식은 제한된 환경에서 문제가 생길 수 있음을 알게 됐다.
- DP를 이용한 문제 해결에서 공간 복잡도를 줄이는 방법을 배우는 계기가 되었다.
- 최종적으로 효율적인 메모리 사용과 간결한 구현으로 최적화할 수 있어 의미 있었다!