[BOJ] 2096 - 내려가기 (Python)

 

 

아이디어

 

1149번 RGB거리와 유사한 문제로, 동적 계획법으로 각 칸에서 가능한 최댓값과 최솟값을 갱신해 나간다.

 

 

풀이

 

min_dp와 max_dp에는 각각 현재 줄에서 각 칸의 가능한 누적 점수 최솟값과 최댓값을 저장하고,

min_prev와 max_prev는 각각 이전 줄까지 각 칸의 누적 점수 최솟값과 최댓값을 저장한다.

 

차례로 숫자 세 개를 a, b, c에 입력 받고, 이전 줄에서 내려올 수 있는 누적 점수와 더해 min_dp와 max_dp를 갱신한다.

min_dp와 max_dp 갱신 이후 min_prev와 max_prev에 각각 현재 min_dp와 max_dp을 저장하고 다음 for문을 진행한다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    max_prev = [0]*3
    min_prev = [0]*3
    max_dp = [0]*3
    min_dp = [0]*3
    for _ in range(N):
        a, b, c = map(int, input().split())
        min_dp[0] = min(min_prev[0], min_prev[1])+a
        min_dp[1] = min(min_prev)+b
        min_dp[2] = min(min_prev[1], min_prev[2])+c
        min_prev[0], min_prev[1], min_prev[2] = min_dp[0], min_dp[1], min_dp[2]
        max_dp[0] = max(max_prev[0], max_prev[1])+a
        max_dp[1] = max(max_prev)+b
        max_dp[2] = max(max_prev[1], max_prev[2])+c
        max_prev[0], max_prev[1], max_prev[2] = max_dp[0], max_dp[1], max_dp[2]
    print(max(max_dp), min(min_dp))

solution()

 

 

슬라이싱을 이용하면 코드를 더 짧게 작성할 수 있으나 더 느렸다.

# 더 느린 코드
a, b, c = map(int, input().split())
min_dp[0] = min(min_prev[:2])+a
min_dp[1] = min(min_prev)+b
min_dp[2] = min(min_prev[1:])+c
min_prev = min_dp[:]
max_dp[0] = max(max_prev[:2])+a
max_dp[1] = max(max_prev)+b
max_dp[2] = max(max_prev[1:])+c
max_prev = max_dp[:]