(Python/🥇5)백준알고리즘 2096번: 내려가기

 

문제 바로가기 

문제

 

문제:

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다.

 

설명1

바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력:

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

 

출력:

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

 

풀이:

틀림풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
lst = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(n)]
dp = [lst[0]] + [[0] * 3 for _ in range(n - 1)]
min_dp = [lst[0]] + [[0] * 3 for _ in range(n - 1)]
for i in range(1, n):
    for j in range(n):
        if j == 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 1]) + lst[i][j]
        elif j == 1:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + lst[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + lst[i][j]
for i in range(1, n):
    for j in range(n):
        if j == 0:
            min_dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + lst[i][j]
        elif j == 1:
            min_dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + lst[i][j]
        else:
            min_dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + lst[i][j]
print(max(dp[-1]),min(dp[-1]))

 

기존 풀이대로 dp를 사용하면 메모리 초과가 난다.

 

그래서 이 전 최댓값을 저장해놓는 식으로 간다 어떻게 보면 슬라이딩 윈도우같은느낌?

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
lst = list(map(int, sys.stdin.readline().split()))
dp = lst
min_dp = lst

for _ in range(n - 1):
    input_list = list(map(int, sys.stdin.readline().split(" ")))

    dp = [input_list[0] + max(dp[0], dp[1]), input_list[1] + max(dp), input_list[2] + max(dp[1], dp[2])]
    min_dp = [input_list[0] + min(min_dp[0], min_dp[1]), input_list[1] + min(min_dp), input_list[2] + min(min_dp[1], min_dp[2])]
print(max(dp),min(min_dp))

 

dp , mindp 에 있는 값들에서 최솟값 최댓값과 지금 들어온 값을 더했을때

 

최소인지, 최대인지 확인해서 배열을 하나씩 증가해주면된다.