🥚문제링크

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

• 다이나믹 프로그래밍
• 슬라이딩 윈도우

아이디어를 떠올리는 것은 어렵지 않았으나 메모리 초과에 걸려 몇 번 다시 풀어본 문제

---

🍳코드

import sys
input = sys.stdin.readline

N = int(input().strip())
arr = [list(map(int, input().split())) for _ in range(N)]

max_dp = [arr[0][0], arr[0][1], arr[0][2]]
min_dp = [arr[0][0], arr[0][1], arr[0][2]]

for i in range(1, N):
    zero, one, two = map(int, max_dp)
    max_dp[0] = arr[i][0] + max(zero, one)
    max_dp[1] = arr[i][1] + max(zero, one, two)
    max_dp[2] = arr[i][2] + max(one, two)

    zero, one, two = map(int, min_dp)
    min_dp[0] = arr[i][0] + min(zero, one)
    min_dp[1] = arr[i][1] + min(zero, one, two)
    min_dp[2] = arr[i][2] + min(one, two)

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

---

🧂아이디어

DP

• 최대값을 구하는 max_dp, 최소값을 구하는 min_dp를 각각 3개의 원소를 가지는 1차원 리스트로 만든다.

• N개의 줄을 내려오면서 idx가 0인 컬럼의 최대/최소값, idx가 1인 컬럼의 최대/최소값, idx가 1인 컬럼의 최대/최소값을 갱신해준다.

• 예를 들어, i번째 줄까지 왔을 때 최대값을 구하는 방법은 아래와 같다.

• 현재 max_dp에는 이전 단계인 i-1번째 줄까지 왔을 때의 idx 0, 1, 2에서의 최대값이 담겨있다. 이것들을 각각 zero, one, two라는 변수에 저장해둔다.

• 문제에서 제시한 그림의 규칙을 이용해 i번째줄의 최대값을 갱신한다.max_dp[0] = arr[i][0] + max(zero, one)
max_dp[1] = arr[i][1] + max(zero, one, two)
max_dp[2] = arr[i][2] + max(one, two)

• 최소값도 최대값과 유사한 방식으로 구할 수 있다.

슬라이딩 윈도우 🌆

알고리즘 분류에 "슬라이딩 윈도우" 라는 말이 있었는데, 처음 들어봐서 찾아보았다.

간단하게 말해, 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리하는 방법(출처: https://blog.fakecoding.com/archives/algorithm-slidingwindow )이라고 한다.

이 문제에서는 N*3의 이차원 리스트를 만들 필요 없이, 3개의 원소만을 가지는 리스트를 유지하며 그 값들을 이용해 계속 갱신해가는 과정이 슬라이딩 윈도우를 이용한 것이라고 볼 수 있다.