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
'백준 풀이' 카테고리의 다른 글
[백준/BOJ] - 16928번 python 풀이 - bfs (0) | 2023.08.21 |
---|---|
[백준/BOJ] - 14500번 python 풀이 - dfs (0) | 2023.08.21 |
[백준/BOJ] - 2565번 python 풀이 - dp (0) | 2023.08.20 |
[백준/BOJ] - 10844번 python 풀이 - dp (0) | 2023.08.16 |
[백준/BOJ] - 14889번 python 풀이 - backtracking (1) | 2023.07.02 |