[백준]2096번 내려가기 - python 파이썬 feat.메모리초과 오류 해결

문제

 

 

 

이 문제는 특이하게도 메모리제한이 굉장히 작다.

항상 숫자의 범위만 확인했는데 덕분에 앞으로 메모리제한도 신경써야한다는 것을 깨닫게 되었다.

 

 

틀린코드

n =int(input())
nums = [list(map(int,input().split())) for _ in range(n)]


dp_max = [[0]*3 for _ in range(n)]
dp_max[0][0] = nums[0][0]
dp_max[0][1] = nums[0][1]
dp_max[0][2] = nums[0][2]

dp_min = [[0]*3 for _ in range(n)]
dp_min[0][0] = nums[0][0]
dp_min[0][1] = nums[0][1]
dp_min[0][2] = nums[0][2]

for i in range(1,len(nums)):
    for j in range(3):
        if j == 0:
            dp_max[i][j] = nums[i][j] + max(dp_max[i-1][0],dp_max[i-1][1])
            dp_min[i][j] = nums[i][j] + min(dp_min[i-1][0],dp_min[i-1][1])
        elif j == 1:
            dp_max[i][j] = nums[i][j] + max(dp_max[i-1][0],dp_max[i-1][1],dp_max[i-1][2])
            dp_min[i][j] = nums[i][j] + min(dp_min[i-1][0],dp_min[i-1][1],dp_min[i-1][2])
        elif j == 2:
            dp_max[i][j] = nums[i][j] + max(dp_max[i-1][1],dp_max[i-1][2])
            dp_min[i][j] = nums[i][j] + min(dp_min[i-1][1],dp_min[i-1][2])
        
mx = max(dp_max[-1])      
mn = min(dp_min[-1])

print(mx,mn)

 

n =int(input())
nums = [list(map(int,input().split())) for _ in range(n)]


dp = [[[0,0] for _ in range(3)] for _ in range(n)]
dp[0][0][0] = nums[0][0]
dp[0][1][0] = nums[0][1]
dp[0][2][0] = nums[0][2]

dp[0][0][1] = nums[0][0]
dp[0][1][1] = nums[0][1]
dp[0][2][1] = nums[0][2]

for i in range(1,len(nums)):
    for j in range(3):
        if j == 0:
            dp[i][j][0] = nums[i][j] + max(dp[i-1][0][0],dp[i-1][1][0])
            dp[i][j][1] = nums[i][j] + min(dp[i-1][0][1],dp[i-1][1][1])
        elif j == 1:
            dp[i][j][0] = nums[i][j] + max(dp[i-1][0][0],dp[i-1][1][0],dp[i-1][2][0])
            dp[i][j][1] = nums[i][j] + min(dp[i-1][0][1],dp[i-1][1][1],dp[i-1][2][1])
        elif j == 2:
            dp[i][j][0] = nums[i][j] + max(dp[i-1][2][0],dp[i-1][1][0])
            dp[i][j][1] = nums[i][j] + min(dp[i-1][2][1],dp[i-1][1][1])
        
mx = float('-inf')    
mn = float('inf')    
for i in range(3):
    if mx < dp[-1][i][0]:
        mx = dp[-1][i][0]
    if mn > dp[-1][i][1]:
        mn = dp[-1][i][1]
    

print(mx,mn)

 

 

이런식으로 두개의 2차원배열을 두었다가 한개의 3차원배열을 두었다가 다 시도해봤는데 둘다 메모리초과가 발생했다....

 

 

그래서 구글링을 해본결과 슬라이딩 윈도우 라는 기법을 써야한다는 것을 알게되었다.

 

슬라이딩 윈도우란?

 

• dp에서 메모이제이션을 할 때, 사용하지 않는 값을 배열에 저장하지 않고 배열을 새롭게 계속해서 갱신시켜주는 것이다.

 

그렇기 때문에 dp를 1차원배열로 설정해서 한 줄 한 줄 입력받을 때마다 값을 갱신하는 방식으로 구현하여 메모리사용량을 줄여주는 것이다.

 

정답코드

n =int(input())

#한줄만 먼저 입력받고 dp에 저장
nums = list(map(int,input().split()))

maxdp = nums
mindp = nums

for _ in range(n-1):
    nums = list(map(int,input().split()))
    maxdp = [nums[0]+max(maxdp[0],maxdp[1]),nums[1]+max(maxdp[0],maxdp[1],maxdp[2]),nums[2]+max(maxdp[1],maxdp[2])]
    mindp = [nums[0]+min(mindp[0],mindp[1]),nums[1]+min(mindp[0],mindp[1],mindp[2]),nums[2]+min(mindp[1],mindp[2])]


print(max(maxdp),min(mindp))

 

 

 

 

어쩐지 골드5인데 너무 쉽게 술술 풀려서 내 실력이 늘은줄 알았는데........ 메모리관련 문제를 해결하는 게 관건인 문제였다.....ㅎ

 

그래도 알고리즘을 하나 더 배웠다.... 슬라이딩 윈도우를 명심해야지..