[백준 2096] 내려가기

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

2096번: 내려가기

---

접근

각 행에는 3개의 숫자들이 적혀져있다. 이때 첫 번째 숫자는 바로 위에 있는 행 중에 첫 번째, 두 번째 숫자를 선택할 수 있다. 또한 두 번째 숫자는 모든 숫자를 선택할 수 있고, 세 번째 숫자는 두 번째 숫자와 세 번째 숫자를 선택할 수 있다.

 

따라서 두 번째 행부터 탐색을 진행하여 각 열이 선택할 수 있는 숫자 중에서 최댓값과 최솟값을 더해나가서 마지막 행에서 최종 해를 찾는다.

 

여기서 2차원 리스트를 활용하면 메모리 초과가 발생하기 때문에 1차원 리스트로 해결할 수 있는 방법을 생각해야했다.

 

구현

- temp로 되어있는 리스트는 max_board 중 최댓값 또는 최솟값을 더한 값을 저장한다.

- board로 되어있는 리스트에는 현재까지의 계산결과가 저장되어 있다.

N = int(input())
max_temp, min_temp = [0] * 3, [0] * 3
max_board, min_board = [0] * 3, [0] * 3

- N번 동안 세 개의 숫자를 입력받아 x, y, z에 저장한다.

- i가 0일 때는 x와 board에서 i와 i+1번째 숫자를 더한다. i가 1, 2일 때도 선택할 수 있는 숫자들을 각각 더한다.

- 이제 temp를 board로 옮긴다.

- 위의 과정을 통해 board에는 해가 될 수 있는 후보들이 저장된다.

for _ in range(N):
    x, y, z = map(int, input().split())
    for i in range(3):
        if i == 0:
            max_temp[i] = x + max(max_board[i], max_board[i+1])
            min_temp[i] = x + min(min_board[i], min_board[i+1])
        elif i == 1:
            max_temp[i] = y + max(max_board[i-1], max_board[i], max_board[i+1])
            min_temp[i] = y + min(min_board[i-1], min_board[i], min_board[i+1])
        elif i == 2:
            max_temp[i] = z + max(max_board[i-1], max_board[i])
            min_temp[i] = z + min(min_board[i-1], min_board[i])
    for i in range(3):
        max_board[i] = max_temp[i]
        min_board[i] = min_temp[i]

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
max_temp, min_temp = [0] * 3, [0] * 3
max_board, min_board = [0] * 3, [0] * 3

for _ in range(N):
    x, y, z = map(int, input().split())
    for i in range(3):
        if i == 0:
            max_temp[i] = x + max(max_board[i], max_board[i+1])
            min_temp[i] = x + min(min_board[i], min_board[i+1])
        elif i == 1:
            max_temp[i] = y + max(max_board[i-1], max_board[i], max_board[i+1])
            min_temp[i] = y + min(min_board[i-1], min_board[i], min_board[i+1])
        elif i == 2:
            max_temp[i] = z + max(max_board[i-1], max_board[i])
            min_temp[i] = z + min(min_board[i-1], min_board[i])
    for i in range(3):
        max_board[i] = max_temp[i]
        min_board[i] = min_temp[i]

max_value = max(max_board)
min_value = min(min_board)
print(max_value, min_value)