[백준] 2096 내려가기 (python 파이썬)

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

2096번: 내려가기

메모리 제한(4MB)이 있는 dp문제

---

아이디어

1. 메모리 제한

• 매우 적은 메모리 제한을 보고 dp를 사용하기로 결정
• 단순히 문제에 주어진 N값만 보고 배열을 만들기엔 4MB로는 턱없이 부족하다.
• 따라서 임시로 저장해주는 변수를 따로 만들어 사용

 

---

코드 설명

max_arr = [int(x) for x in sys.stdin.readline().rstrip().split()]
min_arr = copy.copy(max_arr)

max_temp = copy.copy(max_arr)
min_temp = copy.copy(max_arr)

먼저 초기 설정.

파이썬에 있는 copy라이브러리로 복사했다.

얕은 복사를 해도 괜찮아서 그냥 copy 함.(변수가 immutable 하니까)

 

메모리가 제한이 있어서 임시로 최댓값, 최솟값을 담아줄 수 있는 temp리스트를 추가로 선언했다.

리스트의 크기는 3으로 각 칸에서 나올 수 있는 최댓값, 최솟값을 자리에 맞게 업데이트해가면 된다.

 

for _ in range(N - 1):
    b1, b2, b3 = map(int, sys.stdin.readline().rstrip().split())

    max_arr[0] = b1 + max(max_temp[0], max_temp[1])
    max_arr[1] = b2 + max(max_temp[0], max_temp[1], max_temp[2])
    max_arr[2] = b3 + max(max_temp[1], max_temp[2])

    min_arr[0] = b1 + min(min_temp[0], min_temp[1])
    min_arr[1] = b2 + min(min_temp[0], min_temp[1], min_temp[2])
    min_arr[2] = b3 + min(min_temp[1], min_temp[2])

    max_temp = copy.copy(max_arr)
    min_temp = copy.copy(min_arr)

이미 입력을 한번 받았기 때문에 N - 1만큼 입력 받으면 된다.

 

먼저 문제에 조건에 따라 첫번째, 두 번째, 세 번째 칸에 올 수 있는 값들을 각각 비교해서 저장하면 된다.

비교하려면 이전 최댓값, 최솟값을 따로 저장해둬야 하므로 temp리스트에 업데이트해준다.

 

---

전체 코드

import sys, copy
N = int(input())

max_arr = [int(x) for x in sys.stdin.readline().rstrip().split()]
min_arr = copy.copy(max_arr)

max_temp = copy.copy(max_arr)
min_temp = copy.copy(max_arr)

for _ in range(N - 1):
    b1, b2, b3 = map(int, sys.stdin.readline().rstrip().split())

    max_arr[0] = b1 + max(max_temp[0], max_temp[1])
    max_arr[1] = b2 + max(max_temp[0], max_temp[1], max_temp[2])
    max_arr[2] = b3 + max(max_temp[1], max_temp[2])

    min_arr[0] = b1 + min(min_temp[0], min_temp[1])
    min_arr[1] = b2 + min(min_temp[0], min_temp[1], min_temp[2])
    min_arr[2] = b3 + min(min_temp[1], min_temp[2])

    max_temp = copy.copy(max_arr)
    min_temp = copy.copy(min_arr)

print(max(max_arr), min(min_arr))

copy라이브러리를 사용 안 하고 min_arr = max_arr [:] 이런 식으로 복사해도 괜찮다.