2096. [Python]내려가기

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 4MB
• 다이나믹 프로그래밍

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

N = int(input())

first = list(map(int,input().split()))

max_dp = first
min_dp = first
# 최대값 최소값 저장
for _ in range(N-1):
    a, b, c = map(int,input().split())
    max_a = max(max_dp[0],max_dp[1]) + a
    max_b = max(max_dp[0], max_dp[1], max_dp[2]) + b
    max_c = max(max_dp[1], max_dp[2]) + c
    min_a = min(min_dp[0], min_dp[1]) + a
    min_b = min(min_dp[0], min_dp[1], min_dp[2]) + b
    min_c = min(min_dp[2], min_dp[1]) + c
    max_dp = [max_a, max_b, max_c]
    min_dp = [min_a, min_b, min_c]

print(max(max_dp), min(min_dp))

 

4. 문제를 풀고난 후 생각

 

• 3칸을 고정으로 하고 각 지점에서 아래로 가며 양옆의 값중 더해서 최종적으로 최소값 최대값을 구하는 문제이다.
• a, b, c 값을 각각 정해두고 max 와 min 을 저장할 리스트를 생성해둔다.
• 반복문을 돌면서 값을 max 와 min 을 갱신해가며 최종적으로 max 값과 min 값을 출력해주면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 다이나믹 프로그래밍