백준 2096: 내려가기

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

알고리즘 분석

• 이건 문제 안 읽어봐도 제목으로 유추가 가능하다
• 내려가기 -> 내려가며 이전 최적해를 바탕으로 값 계산하기 -> dp

입출력 분석

• 시간 제한은 1초이며, N은 100,000이다. dp 쓰면 무조건 풀리는 문제
• 메모리 제한은 4MB인데, N이 100,000이다.
• 파이썬에서 int는 28bytes를 차지한다. 따라서 정수 데이터만 고려해도 100,000 * 3 * 28 = 8.4MB로 메모리 초과가 발생한다.
• 따라서 이 문제는 입력을 받는 즉시 계산하고 어디 저장하지 말라는 뜻이다

---

점화식 세우기

i번째 열에서 내려가려면 다음과 같은 경우의 수가 존재한다.

• 첫 번째 칸의 경우
  - 첫 번째, 두 번째 가능
• 두 번째 칸의 경우
  - 모든 칸 가능
• 세 번째 칸의 경우
  - 두 번째, 세 번째 가능

이를 고려하면 다음과 같이 수도 코드를 작성할 수 있다.

res_max[i][0] = max(res[i-1][0], res[i-1][1]) + arr[i][0]
res_max[i][1] = max(res[i-1][0], res[i-1][1], res[i-1][2]) + arr[i][1]
res_max[i][2] = max(res[i-1][1], res[i-1][2]) + arr[i][2]

res_min[i][0] = min(res[i-1][0], res[i-1][1]) + arr[i][0]
res_min[i][1] = min(res[i-1][0], res[i-1][1], res[i-1][2]) + arr[i][1]
res_min[i][2] = min(res[i-1][1], res[i-1][2]) + arr[i][2]

하지만 이 문제는 배열을 통해 이전의 값을 기억할 필요가 없다.

따라서 변수만 사용해 다음과 같이 메모리를 줄일 수 있다.

min_l, min_m, min_r = min(res[i-1][0], res[i-1][1]) + arr[i][0], min(res[i-1][0], res[i-1][1], res[i-1][2]) + arr[i][1], min(res[i-1][1], res[i-1][2]) + arr[i][2]

max_l, max_m, max_r = max(res[i-1][0], res[i-1][1]) + arr[i][0], max(res[i-1][0], res[i-1][1], res[i-1][2]) + arr[i][1], max(res[i-1][1], res[i-1][2]) + arr[i][2]

---

풀이

import sys  
  
input = sys.stdin.readline  
  
n = int(input())  
  
first_l, first_m, first_r = map(int, input().split())  
  
min_l, min_m, min_r = first_l, first_m, first_r  
max_l, max_m, max_r = first_l, first_m, first_r  
  
for _ in range(n - 1):  
    now_l, now_m, now_r = map(int, input().split())  
    min_l, min_m, min_r = min(min_l, min_m) + now_l, min(min_l, min_m, min_r) + now_m, min(min_m, min_r) + now_r  
    max_l, max_m, max_r = max(max_l, max_m) + now_l, max(max_l, max_m, max_r) + now_m, max(max_m, max_r) + now_r  
  
print(max(max_l, max_m, max_r), min(min_l, min_m, min_r))

---

결과

제한 조건을 잘 읽고 점화식을 잘 세우면 어렵지 않은 문제였다.