[파이썬] 백준 2096: 내려가기 (골드5)

[파이썬] 백준 2096: 내려가기 (골드5)

2096번: 내려가기

---

문제

---

풀이

0. 방향성 생각

• 메모리가 4MB이다. 3*N 리스트를 작성하지 않고 현재 최대값, 최소값만 기억한다.

 

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())

arr_max,arr_min = [0]*3,[0]*3
temp_max,temp_min = [0]*3,[0]*3

• for문을 돌면서 현재 arr_max, arr_min을 업데이트 시키면 구하는 값과 달라질 수 있다.
• 이를 방지하기 위해 temp에 저장해놓고 for문의 마지막에 다시 arr_max, arr_min에 할당하는 방식으로 작성한다.

 

2. DP

for i in range(n):
    arr = list(map(int,input().split()))
    
    temp_max[0] = arr[0] + max(arr_max[0],arr_max[1])
    temp_min[0] = arr[0] + min(arr_min[0],arr_min[1])
    
    temp_max[1] = arr[1] + max(arr_max)
    temp_min[1] = arr[1] + min(arr_min)
    
    temp_max[2] = arr[2] + max(arr_max[1],arr_max[2])
    temp_min[2] = arr[2] + min(arr_min[1],arr_min[2])
    
    arr_max = temp_max[:]
    arr_min = temp_min[:]
    
print(max(arr_max),min(arr_min))

• 현재 arr값을 받는다.
• temp_max[0]에는 이전 arr_max[:1] 중 큰 값을 선택한다. 최솟값도 비슷한 방식으로 업데이트한다.
• temp_max[1]에는 이전 arr_max 중 큰 값을 선택한다. 최솟값도 비슷한 방식으로 업데이트한다.
• temp_max[2]에는 이전 arr_max[1:] 중 큰 값을 선택한다. 최솟값도 비슷한 방식으로 업데이트한다.
• temp_max가 업데이트 됐으면 arr_max에 복사해준다. 참조 오류 방지를 위해 [:] 사용.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())

arr_max,arr_min = [0]*3,[0]*3
temp_max,temp_min = [0]*3,[0]*3

for i in range(n):
    arr = list(map(int,input().split()))
    
    temp_max[0] = arr[0] + max(arr_max[0],arr_max[1])
    temp_min[0] = arr[0] + min(arr_min[0],arr_min[1])
    
    temp_max[1] = arr[1] + max(arr_max)
    temp_min[1] = arr[1] + min(arr_min)
    
    temp_max[2] = arr[2] + max(arr_max[1],arr_max[2])
    temp_min[2] = arr[2] + min(arr_min[1],arr_min[2])
    
    arr_max = temp_max[:]
    arr_min = temp_min[:]
    
print(max(arr_max),min(arr_min))

 

이건 메모리 제한 안봤을 때 처음 풀이.

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
dp_max = [[0]*3 for _ in range(n)]
dp_min = [[0]*3 for _ in range(n)]
dp_max[0],dp_min[0] = arr[0],arr[0]

answer = []
for stage in range(n-1):
    for lane in range(3):
        now = arr[stage+1][lane]
        if lane == 0:
            dp_max[stage+1][lane] = now + max(dp_max[stage][0],dp_max[stage][1])
            dp_min[stage+1][lane] = now + min(dp_min[stage][0],dp_min[stage][1])
        elif lane == 1:
            dp_max[stage+1][lane] = now + max(dp_max[stage])
            dp_min[stage+1][lane] = now + min(dp_min[stage])
        else:
            dp_max[stage+1][lane] = now + max(dp_max[stage][1],dp_max[stage][2])
            dp_min[stage+1][lane] = now + min(dp_min[stage][1],dp_min[stage][2])

print(max(dp_max[-1]),min(dp_min[-1]))