[백준 2096 / Python] 내려가기

 

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

2096번: 내려가기

접근방식

dp 배열을 만들어서 dp[현재위치값] = 현재 위치값+ max(이동할 수 있는 위치 값) 으로 값을 갱신하며 최대,최솟값을 구한다.

 

처음 풀이

import sys
input = sys.stdin.readline

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] = arr[0]
dp_min[0] = arr[0]

for i in range(1, n):
    dp_max[i][0] = max(arr[i][0] + dp_max[i - 1][0], arr[i][0] + dp_max[i - 1][1])
    dp_max[i][1] = max(arr[i][1] + dp_max[i - 1][0], arr[i][1] + dp_max[i - 1][1], arr[i][1] + dp_max[i - 1][2])
    dp_max[i][2] = max(arr[i][2] + dp_max[i - 1][1], arr[i][2] + dp_max[i - 1][2])

    dp_min[i][0] = min(arr[i][0] + dp_min[i - 1][0], arr[i][0] + dp_min[i - 1][1])
    dp_min[i][1] = min(arr[i][1] + dp_min[i - 1][0], arr[i][1] + dp_min[i - 1][1], arr[i][1] + dp_min[i - 1][2])
    dp_min[i][2] = min(arr[i][2] + dp_min[i - 1][1], arr[i][2] + dp_min[i - 1][2])

max_result = max(dp_max[n - 1])
min_result = min(dp_min[n - 1])
print(str(max_result) + " " + str(min_result))

테스트케이스는 통과되었지만, 메모리제한으로 인해 메모리초과가 되었다.

그래서 위의 코드에서 배열을 선언하지 않고, 입력값을 두 번 받아 메모리 초과를 해결했다.

 

풀이 코드

import sys
input = sys.stdin.readline

n = int(input())
# 메모리 제한으로 첫 줄 입력 값을 dp에 갱신
a, b, c = map(int, input().split())
dp_max = [[0] * 3 for _ in range(n)]
dp_min = [[0] * 3 for _ in range(n)]

dp_max[0] = [a,b,c]
dp_min[0] = [a,b,c]

for i in range(1, n):
    a, b, c = map(int, input().split())
    dp_max[i][0] = max(a + dp_max[i - 1][0], a + dp_max[i - 1][1])
    dp_max[i][1] = max(b + dp_max[i - 1][0], b + dp_max[i - 1][1], b + dp_max[i - 1][2])
    dp_max[i][2] = max(c + dp_max[i - 1][1], c + dp_max[i - 1][2])

    dp_min[i][0] = min(a + dp_min[i - 1][0], a + dp_min[i - 1][1])
    dp_min[i][1] = min(b + dp_min[i - 1][0], b + dp_min[i - 1][1],b + dp_min[i - 1][2])
    dp_min[i][2] = min(c + dp_min[i - 1][1], c + dp_min[i - 1][2])

max_result = max(dp_max[n - 1])
min_result = min(dp_min[n - 1])
print(max_result,min_result)