[Baekjoon] 2096. 내려가기

3 minute read

문제 설명

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

18 6

예제 입력 2

예제 출력 2

0 0

출처

빠진 조건을 찾은 사람: dreamian
잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

메모리 제한

Java 8: 256 MB
Java 8 (OpenJDK): 256 MB
Java 11: 256 MB
Kotlin (JVM): 256 MB

문제 풀이

# Dynamic Programming

Dynamic Programming 문제입니다.

풀이 과정

보자마자 동적계획법이라는 것을 알아채는 것은 쉬운데, 비슷한 문제를 풀어보지 않았다면 메모리 초과 문제 때문에 시간이 좀 걸릴 수도 있는 문제.

우선 이 문제는 메모리 조건을 만족시키는 것이 관건이고, 이를 위해 슬라이딩 윈도우 기법을 사용한다.

전체 코드

1번 풀이: 메모리 초과

처음에는 그냥 일반적인 동적계획법 문제를 풀듯이 풀었다.

입력을 board로 먼저 받고, 내려가면서 최대/최소값을 계산한다.

import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
    board.append([[num,num] for num in map(int, input().rstrip().split())]) # max, min

for i in range(1,N):
    board[i][0] = [board[i][0][0]+max([mx for mx,mn in board[i-1][:2]]), board[i][0][1]+min([mn for mx,mn in board[i-1][:2]])]
    board[i][1] = [board[i][1][0]+max([mx for mx,mn in board[i-1]]), board[i][1][1]+min([mn for mx,mn in board[i-1]])]
    board[i][2] = [board[i][2][0]+max([mx for mx,mn in board[i-1][1:]]), board[i][2][1]+min([mn for mx,mn in board[i-1][1:]])]
print(max([mx for mx,mn in board[-1]]), min([mn for mx,mn in board[-1]]))

2번 풀이: 성공

그러나 1번 풀이처럼 전체 입력을 2차원 리스트로 모두 받으면 메모리 초과가 발생한다.

따라서, 입력을 받으면서 최대/최소값을 계산해야 한다.

그리고 이를 아래와 같이 구현했다. 사용하는 리스트는 3개이다.

values: 현재 line의 입력
prev_scores: 이전 line 까지의 최대/최소값
cur_scores: 현재 line 까지의 최대/최소값

import sys
input = sys.stdin.readline
N = int(input())

from copy import deepcopy
values = list(map(int, input().rstrip().split()))
prev_scores = [[num,num] for num in values] # max, min
cur_scores = [[num,num] for num in values] # max, min
for i in range(1,N):
    values = list(map(int, input().rstrip().split()))
    cur_scores[0] = [values[0]+max([mx for mx,mn in prev_scores[:2]]), values[0]+min([mn for mx,mn in prev_scores[:2]])]
    cur_scores[1] = [values[1]+max([mx for mx,mn in prev_scores]), values[1]+min([mn for mx,mn in prev_scores])]
    cur_scores[2] = [values[2]+max([mx for mx,mn in prev_scores[1:]]), values[2]+min([mn for mx,mn in prev_scores[1:]])]
    prev_scores = deepcopy(cur_scores)
print(max([mx for mx,mn in cur_scores]), min([mn for mx,mn in cur_scores]))

참고

코드가 간결해질 줄 알고 [max, min]과 같이 최대값과 최소값을 동시에 저장하도록 했지만, 오히려 가독성이 떨어진다.

그냥 아래와 같이 이전 max/min 저장, 현재 max/min 저장하는 리스트를 따로 만들어주는 것이 더 나은 것 같다.

출처: https://kyun2da.github.io/2021/04/27/goDown/

import sys

input = sys.stdin.readline

n = int(input())

max_dp = [0] * 3
min_dp = [0] * 3

max_tmp = [0] * 3
min_tmp = [0] * 3

for i in range(n):
    a, b, c = map(int, input().split())
    for j in range(3):
        if j == 0:
            max_tmp[j] = a + max(max_dp[j], max_dp[j + 1])
            min_tmp[j] = a + min(min_dp[j], min_dp[j + 1])
        elif j == 1:
            max_tmp[j] = b + max(max_dp[j - 1], max_dp[j], max_dp[j + 1])
            min_tmp[j] = b + min(min_dp[j - 1], min_dp[j], min_dp[j + 1])
        else:
            max_tmp[j] = c + max(max_dp[j], max_dp[j - 1])
            min_tmp[j] = c + min(min_dp[j], min_dp[j - 1])

    for j in range(3):
        max_dp[j] = max_tmp[j]
        min_dp[j] = min_tmp[j]

print(max(max_dp), min(min_dp))

배운 점

슬라이딩 윈도우 기법은 동적 계획법 문제에서 메모리 사용량을 줄일 때 사용한다.
- 입력을 한 번에 모두 받지 않고, 받으면서 계산한다!

Share on

Twitter Facebook LinkedIn

wowo0709