[BOJ][Python]2096 풀이

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

2096번: 내려가기

import sys
ssr = sys.stdin.readline

def max_dp():
    scores = [board[0][0], board[0][1], board[0][2]]
    dpos = (-1, 0, 1)
    for r in range(n):
        if r == n-1:
            break
        tmps = [i for i in scores]
        scores = [tmps[i]+board[r+1][i] for i in range(3)]
        for c in range(3):
            for dc in dpos:
                if 0 <= c+dc < 3:
                    scores[c+dc] = max(tmps[c]+board[r+1][c+dc], scores[c+dc])
    return max(scores)
                    
def min_dp():
    scores = [board[0][0], board[0][1], board[0][2]]
    dpos = (-1, 0, 1)
    for r in range(n):
        if r == n-1:
            break
        tmps = [i for i in scores]
        scores = [tmps[i]+board[r+1][i] for i in range(3)]
        for c in range(3):
            for dc in dpos:
                if 0 <= c+dc < 3:
                    scores[c+dc] = min(tmps[c]+board[r+1][c+dc], scores[c+dc])
    return min(scores)

n = int(ssr())
board = [list(map(int, ssr().split())) for _ in range(n)]
print(max_dp(), min_dp())

 

예전에 이런 비슷한 문제를 bfs로 풀었던 적이 있는데요. 이번에는 그 때랑 다르게 메모리 제한이 4mb로 보통 문제들보다 좀 타이트합니다. 그래서 bfs는 사용하기 힘들고 최대한 사용 메모리를 줄여서 dp로 풀어봤습니다. 아마도 bfs로 풀지 말라고 메모리를 타이트하게 주는 것 같네요.

 

풀이법이 dp라고 바로 떠올릴 수 있는 건 전에 이런 문제를 풀어봤던 것도 있지만, 최댓값이나 최솟값을 구하기 위해서는 결국 모든 조합을 다 시도해야하기 때문입니다. 그리디로 풀지 못하는 이유와도 같겠네요. 순간 순간의 최댓값이나 최솟값을 구했을 때는 1번 위치나 3번 위치에 있을 때 못가는 곳이 생기기 때문입니다.