[Python] BOJ / 2096번/ 내려가기

2096번: 내려가기

📝 문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

 

📜 풀이

• DP 알고리즘을 사용하여 풀이할 수 있음
• 메모리 제한이 4MB이므로, 더 이상 사용하지 않는 DP 배열의 값을 저장해놓지 않고 갱신하는 방식으로 구현해야함
• 접근 방식은 다음과 같음
  • n행까지의 합을 구했을 때 그 합이 최대 또는 최소가 되도록 계산한 값을 저장하는 배열을 dp라고 할 때, dp[i]에서의 i는 열(0, 1, 2)을 의미한다.
  • 즉, 문제에 제시된 조건에 따르면 dp[0]은 바로 이전 프로세스에서 dp[0] 또는 dp[1] 중 최대 또는 최솟값과 특정 위치의 값을 더한 값이 될 것이다.(dp[2]은 관여할 수 없기 때문)
  • 마찬가지로 dp[1]은 바로 이전 프로세스에서 dp[0] 또는 dp[1] 또는 dp[2] 중 최대 또는 최솟값과 특정 위치의 값을 더한 값이 될 것이다.
  • dp[2]의 경우에는 바로 이전 프로세스에서 dp[1] 또는 dp[2] 중 최대 또는 최솟값과 특정 위치의 값을 더한 값이 될 것이다.(dp[1]은 관여할 수 없기 때문)

 

💻 소스코드

import sys
input = sys.stdin.readline

max_dp = [0] * 3
min_dp = [0] * 3

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