백준 15645 내려가기 [dp]

import sys
input = sys.stdin.readline
N = int(input())

dp = [[0 for i in range(3)] for j in range(2)]
smalldp = [[0 for i in range(3)] for j in range(2)]

for i in range(0, N):
    arr = list(map(int, input().split()))
    for j in range(3):
        if j == 0:
            dp[1][j] = arr[j] + max(dp[0][j], dp[0][j+1])
            smalldp[1][j] = arr[j] + min(smalldp[0][j], smalldp[0][j + 1])
        elif j == 1:
            dp[1][j] = arr[j] + max(dp[0][j], dp[0][j-1], dp[0][j+1])
            smalldp[1][j] = arr[j] + min(smalldp[0][j], smalldp[0][j-1], smalldp[0][j+1])
        else:
            dp[1][j] = arr[j] + max(dp[0][j], dp[0][j-1])
            smalldp[1][j] = arr[j] + min(smalldp[0][j], smalldp[0][j-1])
    for j in range(3):
        dp[0][j] = dp[1][j]
        smalldp[0][j] = smalldp[1][j]

print(max(dp[-1]), min(smalldp[-1]))

메모리와 시간제한에 신경써야했던 문제. 입력값은 따로 배열로 받는 것이 아닌 포문 내에서 받을때마다 처리하도록 했고 dp는 슬라이딩 방식을 통해 2*3 짜리 배열 2개로만 해결했다.

 

시간 줄이기

이번 문제 풀면서 내장함수 함부로 사용하는거 아님을 되새겼다. 처음엔 copy로 슬라이딩했는데 시간초과였다.

for j in range(3):
  dp[0][j] = dp[1][j]
  smalldp[0][j] = smalldp[1][j]
  

dp[0] = dp[1].copy()
smalldp[0] = smalldp[1].copy()

그 다음은 input() 대신에 sys.stdin.readline() 으로 입력받았더니 속도가 약 8배 줄었다.