[BOJ][🟡4][백준#02096] 내려가기

문제 출처

BAEKJOON Online Judge #2096

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

예제

예제 1

입력

3
1 2 3
4 5 6
4 9 0

출력

18 6

예제 2

입력

3
0 0 0
0 0 0
0 0 0

출력

0 0

My Sol

import sys
input = sys.stdin.readline

N = int(input())
startlst = list(map(int, input().split()))
maxlst = startlst[::]
minlst = startlst[::]

i = 1
while i < N:
    a, b, c = map(int, input().split())
    maxL = max(maxlst[0], maxlst[1])
    maxR = max(maxlst[1], maxlst[2])
    maxC = max(maxL, maxR)
    minL = min(minlst[0], minlst[1])
    minR = min(minlst[1], minlst[2])
    minC = min(minL, minR)

    maxlst[0] = a + maxL
    maxlst[1] = b + maxC
    maxlst[2] = c + maxR
    minlst[0] = a + minL
    minlst[1] = b + minC
    minlst[2] = c + minR
    i += 1

print(max(maxlst), min(minlst))

DP를 사용하는 문제이지만, 사실상 하드코딩에 가까울 정도로 어려울 게 없는 문제였다. 그냥 문제에서 요구한대로 위쪽에 있는 값 중 선택할 수 있는 위치의 값에서 최댓값과 최솟값을 아래 값과 더하며 내려가며 취할 수 있는 가장 큰 값과 작은 값을 위치에 저장해준다. 이후 맨 마지막 줄의 최댓값과 최솟값을 구해 출력하면 되겠다.

단지 메모리 문제를 해결하기 위해 2차원 배열을 사용하는 것이 아니라, 입력 받는 수를 매번 처리해서 3개짜리 배열을 계속 유지하는 것이 핵심이었다.

결과

맞았습니다!!

모범답안

출처

from sys import stdin
input=stdin.readline

n=int(input())
mxdp=[list(map(int,input().split()))]
mndp=mxdp[:]

for i in range(n-1):
    a,b,c=map(int,input().split())
    na,nb,nc=mxdp.pop()
    ma,mb,mc=mndp.pop()
    mxdp.append([a+max(na,nb),b+max(na,nb,nc),c+max(nb,nc)])
    mndp.append([a+min(ma,mb),b+min(ma,mb,mc),c+min(mb,mc)])

print(max(mxdp[0]),min(mndp[0]))