[백준] 2096. 내려가기 풀이 (Python, TypeScript)

2096번: 내려가기

접근한 방법

답을 도출하기 위한 풀이 로직은 쉽지만 메모리, 시간 초과 문제로 인해 정답 비율이 낮은걸로 보입니다. 이 문제를 만약 2개의 배열을 만들어 중간 결과를 저장하는 방식으로 코드를 짰다면 입력 데이터가 클 때 메모리 제한(4mb)에 걸리게 될겁니다. 

 

따라서 입력 데이터의 최댓값과 최솟값을 계산하면서 중간 결과를 저장하는 대신, 이전 단계의 계산 결과만 활용하여 계산해 나가는 방식을 사용하면 풀이할 수 있습니다. 첫 입력 데이터 한 줄을 초깃값으로 정해놓고 다음 입력을 받을 때 각 자리마다 현재의 입력값과 이전 값들 중 최댓값(최솟값)을 만들어주면 됩니다.

 

3
1 2 3
4 5 6
4 9 0

예제 입력1을 예시로 보면 초깃값은 1, 2, 3입니다. 이 값은 최댓값1번, 2번, 3번, 최솟값 1번, 2번, 3번이 됩니다.

다음 입력인 4, 5, 6에서 각 최댓값과 최솟값은 다음과 같이 정할 수 있습니다.

최댓값1번 = 4 + (이전 최댓값1번과 2번중 더 큰 값)

최댓값2번 = 5 + (이전 최댓값1번, 2번, 3번 중 가장 큰 값)

최댓값3번 = 4 + (이전 최댓값2번과 3번중 더 큰 값)

... 최솟값도 마찬가지.

 

이런 방식으로 최종 저장되는 최댓값1번, 2번, 3번 중 가장 큰 값과 최솟값 1번, 2번, 3번 중 가장 작은 값이 정답이 됩니다.

 

Python

import sys
input = sys.stdin.readline

n = int(input())
mx1, mx2, mx3 = map(int, input().split())
mn1, mn2, mn3 = mx1, mx2, mx3

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    pmx1, pmx2, pmx3, pmn1, pmn2, pmn3 = mx1, mx2, mx3, mn1, mn2, mn3
    mx1 = a + max(pmx1, pmx2)
    mx2 = b + max(pmx1, pmx2, pmx3)
    mx3 = c + max(pmx2, pmx3)
    mn1 = a + min(pmn1, pmn2)
    mn2 = b + min(pmn1, pmn2, pmn3)
    mn3 = c + min(pmn2, pmn3)
print(max(mx1, mx2, mx3), min(mn1, mn2, mn3))

TypeScript

function sol2096(n: number, arr: Array<Array<number>>) {
  let [mx1, mx2, mx3] = arr[0];
  let [mn1, mn2, mn3] = arr[0];
  for (let i = 1; i < n; i += 1) {
    const [a, b, c] = arr[i];
    const [pmx1, pmx2, pmx3, pmn1, pmn2, pmn3] = [mx1, mx2, mx3, mn1, mn2, mn3];
    mx1 = a + Math.max(pmx1, pmx2);
    mx2 = b + Math.max(pmx1, pmx2, pmx3);
    mx3 = c + Math.max(pmx2, pmx3);
    mn1 = a + Math.min(pmn1, pmn2);
    mn2 = b + Math.min(pmn1, pmn2, pmn3);
    mn3 = c + Math.min(pmn2, pmn3);
  }
  return [Math.max(mx1, mx2, mx3), Math.min(mn1, mn2, mn3)];
}
console.log(
  sol2096(3, [
    [1, 2, 3],
    [4, 5, 6],
    [4, 9, 0],
  ])
);