[백준] 2096 - 내려가기

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

2096번: 내려가기

문제 한줄 이해

- N줄에 3개의 숫자가 쓰여져 있을 때 첫줄 부터 숫자를 선택해 더해나가면서 최소와 최대인 경우 구하기

 

생각난 풀이

1번째 방법: 며칠전에 RGB거리 문제랑 비슷한 느낌인데 라는 생각에 다이나믹프로그래밍을 떠올렸다.

이때 그때의 아이디어랑 똑같이 풀면 되겠는데? 라는 생각했다.

먼저 수를 고를때 이전에 더해진 값들이 저장된 dp 값중에서 최대와 최소를 구해가자라고 생각했다. 

이때 각자리를 선택할때 각 줄에 수를 선택할때 이미 dp[현재줄-1]에 대한 최대와 최소값을 저장했기 때문에 조건에 주어진 대로 dp값을 고르면 된다.

import sys
n = int(sys.stdin.readline())

dp = [[0 for i in range(n)] for i in range(n+1)]
graph = []
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,n+1):
    dp[i][0] = max(dp[i-1][0],dp[i-1][1]) + graph[i-1][0]
    dp[i][1] = max(dp[i-1][0],dp[i-1][1],dp[i-1][2])+graph[i-1][1]
    dp[i][2] = max(dp[i-1][1],dp[i-1][2])+graph[i-1][2]
print(max(dp[n]), end=' ')

dp = [[0 for i in range(n)] for i in range(n+1)]
for i in range(1,n+1):
    dp[i][0] = min(dp[i-1][0],dp[i-1][1]) + graph[i-1][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][1],dp[i-1][2])+graph[i-1][1]
    dp[i][2] = min(dp[i-1][1],dp[i-1][2])+graph[i-1][2]
print(min(dp[n]))

제출 후 메모리 초과 .... 그래서 조건을 다시 봤더니 메모리 제한이 현저히 낮았다.

 

2번째 방법: 그래서 메모리를 줄이기 위해 고민했다. 메모리를 줄이기 위해서 배열의 저장되는 크기를 최대한 줄이는 방법이 떠올랐다.

그래서 그래프의 정보를 입력 받아 저장하지 않고 바로 처리하는 방법과

dp의 크기를 아래와 같이 줄였다. dp[0]은 최대값을 담기 위한 dp[1]은 최소값을 담기 위한

1번 방법에서 dp에 이전 줄에 누적된 합들을 저장해 그대로 선택만 해서 썼는데 최대값 배열 크기를 [0,0,0]와 같이 줄인 상태에서 어떻게 할 수 있지 고민했다.

그냥 dp[0]에서 큰 값 골라서 넣으면 안돼? 라는 생각을 했지만 맨왼쪽 숫자를 고른 순간 dp의 값이 갱신이 되기때문에 문제가 된다.

그래서 갱신을 해주기 전에 이전에 저장된 값을 보존해주기 위해 값을 따로 담아서 이를 통해 비교해 저장해 나가는 방법을 택했다.

import sys
n = int(sys.stdin.readline())

dp = [[0 for i in range(3)] for i in range(2)]
for i in range(1,n+1):
    now1,now2,now3  = dp[0][0],dp[0][1],dp[0][2]
    a,b,c = map(int,sys.stdin.readline().split())
    dp[0][0] = max(now1,now2) + a
    dp[0][1] = max(now1,now2,now3) + b
    dp[0][2] = max(now2,now3) + c
    now1,now2,now3  = dp[1][0],dp[1][1],dp[1][2]
    dp[1][0] = min(now1,now2) + a
    dp[1][1] = min(now1,now2,now3) + b
    dp[1][2] = min(now2,now3) + c
print(max(dp[0]), min(dp[1]))

통과!