[백준/파이썬] 2096번: 내려가기

문제

https://www.acmicpc.net/problem/2096

풀이

• N개의 줄에 0~9의 숫자가 3개씩 적혀있다.
• 다음 숫자를 선택할 때, 바로 아래의 수로 넘어가거나 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다.

처음 문제를 접했을 때, BFS로 모든 경우의 수를 탐색해서 결괏값을 출력하려고 했습니다.

❌ BFS 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    queue = deque()
    for i in range(3):
        queue.append((0, i, board[0][i]))
        
    mx, mn = 0, 1e9
    
    while queue:
        x,y,total = queue.popleft()
        
        if x == n - 1:
            mx = max(mx, total)
            mn = min(mn, total)
            continue
        
        for dy in (-1, 0, 1):
            ny = y + dy
            if 0 <= ny < 3:
                queue.append((x+1, ny, total + board[x+1][ny]))
    
    return mx, mn

if __name__ == "__main__":
    n = int(input())
    board = [list(map(int,input().split())) for _ in range(n)]
    print(*bfs())

• 그래프에 모든 수 입력
• 큐에 0번 행에 있는 수와 값 삽입
• 그 다음 수를 탐색하여 큐에 삽입
• 마지막 행이라면 최댓값 최솟값 리턴

위와 같은 방식으로 진행했는데

메모리 초과가 발생하더군요..

문제를 다시 살펴보니 메모리가 4MB(‼️)로 제한되어 있었습니다.

그래서 어떻게 해결할까 문제의 알고리즘 분류를 살펴보니 DP, 슬라이딩 윈도우로 되어있더라구요..

그래서 문제에 제시된 제약 조건을 점화식으로 작성했습니다.

• 현재 위치: 선택할 수 있는 수
• (i,0): (i+1, 0), (i+1,1)
• (i,1): (i+1, 0), (i+1, 1), (i+1, 2)
• (i,2): (i+1, 1), (i+1, 2)

최대 점수 점화식

• mx[i][0] = arr[i][0] + max(mx[i-1][0], mx[i-1][1])
• mx[i][1] = arr[i][1] + max(mx[i-1][0], mx[i-1][1], mx[i-1][2])
• mx[i][2] = arr[i][2] + max(mx[i-1][1], mx[i-1][2])

최소 점수 점화식

• mn[i][0] = arr[i][0] + min(mn[i-1][0], mn[i-1][1])
• mn[i][1] = arr[i][1] + min(mn[i-1][0], mn[i-1][1], mn[i-1][2])
• mn[i][2] = arr[i][2] + min(mn[i-1][1], mn[i-1][2])

이 식을 슬라이딩 윈도우 기법을 활용해 다음과 같이 줄여주었습니다.

n = int(input())
arr = list(map(int,input().split()))
mx = arr
mn = arr

• 첫 번째 줄 입력
• 최댓값, 최솟값 설정: 3개의 열 모두 복사

for i in range(n-1):
    arr = list(map(int,input().split()))
    mx = [arr[0] + max(mx[0], mx[1]), arr[1] + max(mx[0], mx[1], mx[2]), arr[2] + max(mx[1], mx[2])]
    mn = [arr[0] + min(mn[0], mn[1]), arr[1] + min(mn[0], mn[1], mn[2]), arr[2] + min(mn[1], mn[2])]
    
print(max(mx), min(mn))

• n-1개의 줄 입력 받으며 최댓값, 최솟값 즉시 갱신

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
mx = arr
mn = arr

for i in range(n-1):
    arr = list(map(int,input().split()))
    mx = [arr[0] + max(mx[0], mx[1]), arr[1] + max(mx[0], mx[1], mx[2]), arr[2] + max(mx[1], mx[2])]
    mn = [arr[0] + min(mn[0], mn[1]), arr[1] + min(mn[0], mn[1], mn[2]), arr[2] + min(mn[1], mn[2])]
    
print(max(mx), min(mn))