[BOJ-2096] 내려가기

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

2096번: 내려가기

---

[풀이]

 

---

[코드]

import sys
input=sys.stdin.readline

N=int(input())
MAP=[ [*map(int, input().strip().split())]for _ in range(N)]

DP_MAX=[ [0]*3 for _ in range(2)]
DP_MIN=[ [0]*3 for _ in range(2)]

DP_MAX[0][0]=DP_MIN[0][0]=MAP[0][0]
DP_MAX[0][1]=DP_MIN[0][1]=MAP[0][1]
DP_MAX[0][2]=DP_MIN[0][2]=MAP[0][2]
    
for now in range(1,N):
    DP_MAX[1][0]=max(DP_MAX[0][0], DP_MAX[0][1])+MAP[now][0]
    DP_MAX[1][1]=max(DP_MAX[0][0], DP_MAX[0][1], DP_MAX[0][2])+MAP[now][1]
    DP_MAX[1][2]=max(DP_MAX[0][1], DP_MAX[0][2])+MAP[now][2]

    DP_MIN[1][0]=min(DP_MIN[0][0], DP_MIN[0][1])+MAP[now][0]
    DP_MIN[1][1]=min(DP_MIN[0][0], DP_MIN[0][1], DP_MIN[0][2])+MAP[now][1]
    DP_MIN[1][2]=min(DP_MIN[0][1], DP_MIN[0][2])+MAP[now][2]

    DP_MAX[0][0]=DP_MAX[1][0]
    DP_MAX[0][1]=DP_MAX[1][1]
    DP_MAX[0][2]=DP_MAX[1][2]

    DP_MIN[0][0]=DP_MIN[1][0]
    DP_MIN[0][1]=DP_MIN[1][1]
    DP_MIN[0][2]=DP_MIN[1][2]
    
print(max(DP_MAX[0]), min(DP_MIN[0]))

---

[시도] 결과: 메모리 초과 받음 ㅠ.ㅠ

 

(N번째 행까지 도달했을 때, 얻은 점수 최댓값 구하기)

N행 0열=> DP_MAX[N][0] = MAP[N][0] + max( DP_MAX[N-1][0] , DP_MAX[N-1][1] )

N행 1열=> DP_MAX[N][1] = MAP[N][1] + max( DP_MAX[N-1][0] , DP_MAX[N-1][1] , DP_MAX[N-1][2] ) 

N행 2열=> DP_MAX[N][2] = MAP[N][2] + max( DP_MAX[N-1][1] , DP_MAX[N-1][2] )

 

(N번째 행까지 도달했을 때, 얻은 점수 최솟값 구하기)

N행 0열=> DP_MIN[N][0] = MAP[N][0] + min( DP_MIN[N-1][0] , DP_MIN[N-1][1] )

N행 1열=> DP_MIN[N][1] = MAP[N][1] + min( DP_MIN[N-1][0] , DP_MIN[N-1][1] , DP_MIN[N-1][2] ) 

N행 2열=> DP_MIN[N][2] = MAP[N][2] + min( DP_MIN[N-1][1] , DP_MIN[N-1][2] )

 

즉 세개의 N행 3열 배열이 필요하다.

N이 100,000 이라면.. 메모리가 초과할만도 하다.

 

(메모리 초과 받은 실패 코드-python3)

import sys
from copy import deepcopy
input=sys.stdin.readline

N=int(input())
MAP=[ [*map(int, input().strip().split())]for _ in range(N)]

DP_MAX=[ [0]*3 for _ in range(N)]
for i in range(3):
    DP_MAX[0][i]=MAP[0][i]
DP_MIN=deepcopy(DP_MAX)
    
for now in range(1,N):
    DP_MAX[now][0]=max(DP_MAX[now-1][0], DP_MAX[now-1][1])+MAP[now][0]
    DP_MAX[now][1]=max(DP_MAX[now-1][0], DP_MAX[now-1][1], DP_MAX[now-1][2])+MAP[now][1]
    DP_MAX[now][2]=max(DP_MAX[now-1][1], DP_MAX[now-1][2])+MAP[now][2]

    DP_MIN[now][0]=min(DP_MIN[now-1][0], DP_MIN[now-1][1])+MAP[now][0]
    DP_MIN[now][1]=min(DP_MIN[now-1][0], DP_MIN[now-1][1], DP_MIN[now-1][2])+MAP[now][1]
    DP_MIN[now][2]=min(DP_MIN[now-1][1], DP_MIN[now-1][2])+MAP[now][2]
print(max(DP_MAX[N-1]), min(DP_MIN[N-1]))

 

[참고] https://yabmoons.tistory.com/173

[ 백준 2096 ] 내려가기 (C++)