백준 2096 내려가기 파이썬

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

2096번: 내려가기

*맨 밑에 AC코드 and 반례 있음*

 

이 문제를 처음 봤을때 저번에 풀었던 R.G.B거리와 매우 비슷하다고 느껴  n개의 길이를 가진 2차원 dp를 2개 만들어 최댓값과 최솟값을 구하려고 했다.

 

->현재 있는 위치[i]에 올 수 있는 전 위치의 값[i-1] + 현재 위치의s[i] 값을 적절하게 비교해주면서 maxdp[i] , mindp[i]를 채운다. 

 

아래 코드를 보면 이해하기 더 쉬울것 같다.

import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int,input().split())) for _ in range(n)]
maxdp = [[0,0,0] for _ in range(n)]
mindp = [[0,0,0] for _ in range(n)]
maxdp[0] = mindp[0] = s[0]
for i in range(1,n):
    mindp[i][0] = min(mindp[i-1][0] +s[i][0],mindp[i-1][1] +s[i][0])
    mindp[i][1] = min(mindp[i-1][0] +s[i][1],mindp[i-1][1] +s[i][1],mindp[i-1][2]+s[i][1])
    mindp[i][2] = min(mindp[i-1][1] +s[i][2],mindp[i-1][2] +s[i][2]) 
    maxdp[i][0] = max(maxdp[i-1][0] +s[i][0],maxdp[i-1][1] +s[i][0])
    maxdp[i][1] = max(maxdp[i-1][0] +s[i][1],maxdp[i-1][1] +s[i][1],maxdp[i-1][2]+s[i][1])
    maxdp[i][2] = max(maxdp[i-1][1] +s[i][2],maxdp[i-1][2] +s[i][2]) 
print(max(maxdp[-1]),min(mindp[-1]))

하지만 길이가 n인 리스트가 2개여서 인지 메모리 초과가 났고 dp값을 갱신해줄때 이전 dp값만 사용한다는 것을 깨달아 아래와 같이 코드를 바꿔주고 코드를 조금 손보니 AC를 받았다.

 

import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int,input().split())) for _ in range(n)]
maxdp = [[0,0,0] for _ in range(2)]
mindp = [[0,0,0] for _ in range(2)]
maxdp[0] = s[0].copy() # copy를 안 해주면 maxdp[0]의 값이 바뀔때 s[0]의 값도 같이 바뀐다.
mindp[0] = s[0].copy() # copy를 안 해주면 mindp[0]의 값이 바뀔때 s[0]의 값도 같이 바뀐다.d
for t in range(1,n):
    i=t%2 #0,1인덱스를 번갈아가며 접근하기 위한 작업
    mindp[i][0] = min(mindp[i-1][0] +s[t][0],mindp[i-1][1] +s[t][0])
    mindp[i][1] = min(mindp[i-1][0] +s[t][1],mindp[i-1][1] +s[t][1],mindp[i-1][2]+s[t][1])
    mindp[i][2] = min(mindp[i-1][1] +s[t][2],mindp[i-1][2] +s[t][2]) 
    maxdp[i][0] = max(maxdp[i-1][0] +s[t][0],maxdp[i-1][1] +s[t][0])
    maxdp[i][1] = max(maxdp[i-1][0] +s[t][1],maxdp[i-1][1] +s[t][1],maxdp[i-1][2]+s[t][1])
    maxdp[i][2] = max(maxdp[i-1][1] +s[t][2],maxdp[i-1][2] +s[t][2])
print(max(maxdp[n%2-1]),min(mindp[n%2-1]))#마지막 내리막길에서 가장 큰 값과 작은 값

아래는 반례이다.

2

1 2 3

3 2 1

답: 5 3

 

4
1 4 8
0 0 2
3 4 1
3 8 7
답: 22 7