백준 2096, 내려가기

문제 설명

N개의 줄에 0부터 9이하의 숫자가 총 3개씩 주어진다. 이때 첫 번째 행에서부터 놀이를 시작하는데, 바로 아래 숫자 혹은 바로 아래와 연결된 숫자로 내려갈 수 있다. 이때 가능한 최댓값과 최솟값을 구하는 문제이다.

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

2096번: 내려가기

여기서 바로 아래의 숫자라는 건 숫자라는 개념의 순서가 아닌 물리적인 위치의 아래를 의미한다. 

문제 풀이

문제집에서는 투 포인터 혹은 슬라이딩 윈도우로 분류가 되어 있지만, dp와 비슷한 유형의 문제였다. 하지만 범위를 3으로 지정한다는 점에서 슬라이딩 윈도우와 비슷한 것일까?

 

아무튼 하나의 행의 열의 수는 3으로 고정이 되어 있기 때문에 위치를 직접 입력해주면 된다.

예를 들어 아래와 같이 숫자가 주어졌다고 하자

1 2 3

4 5 6

4 9 0

(백준에 있는 예시와 똑같은 거다)

 

이때 arr[0][0]의 바로 아래에 위치한 숫자는 4로 위치는 arr[1][0]이 된다. 또한 문제에서 바로 아래의 옆 수를 고려할 수도 있다고 했으니 arr[1][1]도 고려 대상이 된다. 

그리고 arr[0][1]의 경우는 바로 아래의 수가 arr[1][1]이고 해당 위치의 옆 위치는 arr[1][0]과 arr[1][2]가 있다.

마지막으로 arr[0][2]의 바로 아래 수는 arr[1][2]이고 옆에 위치한 수는 arr[1][1]이다.

 

그렇기에 각 위치에서 내려갈 수 있는 위치의 최댓값 혹은 최솟값을 구해서 계속 갱신해주면 된다.

이를 코드로 표현하면 아래와 같이 나온다.

    dpMax = [arr[0]+max(dpMax[0], dpMax[1]), arr[1]+max(dpMax), arr[2]+max(dpMax[1], dpMax[2])]
    dpMin = [arr[0]+max(dpMin[0], dpMin[1]), arr[1] + max(dpMin), arr[2] + min(dpMin[1], dpMin[2])]

 

입력 같은 경우는 반복문을 진행하면서 넣어줘도 되고 그냥 arr을 2차원 배열로 만든 다음에 한 번에 넣어줘도 된다.

코드

python

from sys import stdin

n = int(input())

# arr = list(map(int, stdin.readline().split()))
# dpMax = arr
# dpMin = arr
dpMax = [0 for i in range(3)]
dpMin = [0 for i in range(3)]
arr = []

for i in range(n):
    arr.append(list(map(int, stdin.readline().split())))

dpMax[0] = arr[0][0]
dpMax[1] = arr[0][1]
dpMax[2] = arr[0][2]

dpMin[0] = arr[0][0]
dpMin[1] = arr[0][1]
dpMin[2] = arr[0][2]

for i in range(1, n):
    dpMax = [arr[i][0] + max(dpMax[0], dpMax[1]), arr[i][1] + max(dpMax), arr[i][2] + max(dpMax[1], dpMax[2])]
    dpMin = [arr[i][0] + min(dpMin[0], dpMin[1]), arr[i][1] + min(dpMin), arr[i][2] + min(dpMin[1], dpMin[2])]

# 입력을 받은 다음 바로 구하는 방법
# for i in range(n-1):
    # arr = list(map(int, stdin.readline().split()))
    # dpMax = [arr[0]+max(dpMax[0], dpMax[1]), arr[1]+max(dpMax), arr[2]+max(dpMax[1], dpMax[2])]
    # dpMin = [arr[0]+max(dpMin[0], dpMin[1]), arr[1] + max(dpMin), arr[2] + min(dpMin[1], dpMin[2])]

print(f'{max(dpMax)} {min(dpMin)}')