[BOJ/python] 2096번 내려가기

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

2096번: 내려가기

 

문제 해석

 

RGB 거리와 유사한 문제이다. 다음 줄로 내려갈 때에는 인접해 있어야만 내려갈 수 있다. 그림을 참고하면 좋다!

따라서 최종적으로 최대값과 최소값을 구하는 문제이다.

---

코드

 

# BOJ 2096

# input
n = int(input())
a, b, c = map(int, input().split())
mx1, mx2, mx3 = a, b, c
mi1, mi2, mi3 = a, b, c

for i in range(1, n):
	# 새로 들어온 값
	x, y, z = (map(int, input().split()))

	# 이전 값 저장
	t1, t2, t3 = mx1, mx2, mx3
	# 최대값 갱신
	mx1 = max(t1 + x, t2 + x)
	mx2 = max(t1 + y, t2 + y, t3 + y)
	mx3 = max(t2 + z, t3 + z)

	
	t1, t2, t3 = mi1, mi2, mi3
	mi1 = min(t1 + x, t2 + x)
	mi2 = min(t1 + y, t2 + y, t3 + y)
	mi3 = min(t2 + z, t3 + z)

print(max(mx1, mx2, mx3), min(mi1, mi2, mi3))

---

문제 풀이

 

전형적인 dp문제라서 최소값, 최대값을 구하는 두개의 배열을 만들어 구현했다. 하지만 메모리 초과가 났다.메모리 제한이 4MB이고, N이 최대 100,000만큼 들어올 수 있으니 내가 구현한 코드에서는 총 3개의 배열을 사용했다. 따라서 메모리 초과가 걸릴수 밖에 없었다.

따라서 배열로 입력받지 않고 변수로 모두 입력받아 변수로 해결해 주었다.

mx1, 2, 3의 값을 t1, t2, t3으로 임시로 빼 놓고 입력받은 x, y, c값을 규칙에 따라 mx1, 2, 3의 값으로 갱신해주는 방식으로 구현했다.