본문 바로가기
백준 풀이

[백준/BOJ] - 2096번 python 풀이 - dp

by 반오십 코린이 2023. 8. 20.
728x90

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

 

2096번: 내려가기

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

www.acmicpc.net


맨처음 각각 최댓값, 최솟값을 저장하는 dp1, dp2 2가지를 deepcop를 통해 만들었더니 메모리 초과가 발생하여

파훼법을 생각해보니 굳이 쓰지 않는 값을 dp에 저장하지 않고 그냥 덮어쓰는 방식으로 진행해도 될 거 같다는 판단이 들었다.

import sys,copy
input = sys.stdin.readline
n = int(input())
arr = []

dp = copy.deepcopy(arr)
dp2 = copy.deepcopy(arr)
for i in range(1,n): #행
    for j in range(3): #열
        if j == 1:
            dp[i][j] = max(dp[i-1]) + dp[i][j] #전 행 최댓값 + 본인값
            dp2[i][j] = min(dp2[i-1]) + dp2[i][j] #전 행 최댓값 + 본인값
        elif j == 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j+1]) + dp[i][j]
            dp2[i][j] = min(dp2[i-1][j], dp2[i-1][j+1]) + dp2[i][j]
        elif j == 2:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + dp[i][j]
            dp2[i][j] = min(dp2[i-1][j], dp2[i-1][j-1]) + dp2[i][j]
print(max(dp[-1]), min(dp2[-1]))

이와 같은 방식을 슬라이딩 윈도우라고 한다.

앞서 언급했듯이 더이상 사용하지 않는 배열에 값을 덮어쓰는 것.

공간 할당을 하지 않고 덮어쓰기 때문에 메모리를 아낄 수 있다.

import sys,copy
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split())) #초기값
max_dp = arr
min_dp = arr

for _ in range(n-1): #n행
    arr = list(map(int,input().split()))
    max_dp = [arr[0] + max(max_dp[0],max_dp[1]), arr[1] + max(max_dp), arr[2] + max(max_dp[1], max_dp[2])]
    min_dp = [arr[0] + min(min_dp[0],min_dp[1]), arr[1] + min(min_dp), arr[2] + min(min_dp[1], min_dp[2])]
print(max(max_dp), min(min_dp))

 

 

 

728x90