[백준 2096번] 파이썬 - 내려가기

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

2096번: 내려가기

 

 

# 조건

• N줄에 0이상 9이하의 숫자가 세 개씩 적혀 있다.
• 첫 줄에서 시작하여 마지막 줄에서 끝나게 되는 놀이이다.
• 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다.
• 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 아래와 같은 제약 조건이 있다.
• 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어있는 수로만 이동할 수 있다.

 

• 별표는 현재 위치, 파란 동그라미가 내려갈 수 있는 위치 이며, 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하여라.

 

# 접근 방법

• dp를 이용하여 풀어주면 된다.
• 1행을 채워준 후, 각 자리에서 내려가면서
• 최댓값과 최소값을 기록해준다.

 

메모리 초과

• 4MB의 제한이 있는데
• 모든 결과값을 저장해두니 메모리 초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
N = int(input())  
num = [[*map(int, input().split())] for _ in range(N)]  
  
dp = [[[0,0] for _ in range(N)] for _ in range(N)]  
for i in range(N):  
    dp[0][i][0] = num[0][i]  
    dp[0][i][1] = num[0][i]  
  
for j in range(1, N):  
    for k in range(N):  
        if k == 0:  
            dp[j][k][0] = min(num[j][k]+dp[j-1][k][0], num[j][k]+dp[j-1][k+1][0])  
            dp[j][k][1] = max(num[j][k] + dp[j - 1][k][1], num[j][k] + dp[j - 1][k + 1][1])  
        elif k == 2:  
  
            dp[j][k][0] = min(num[j][k] + dp[j - 1][k][0], num[j][k] + dp[j - 1][k -1 ][0])  
            dp[j][k][1] = max(num[j][k] + dp[j - 1][k][1], num[j][k] + dp[j - 1][k -1 ][1])  
  
        elif k == 1:  
  
            dp[j][k][0] = min(num[j][k] + dp[j - 1][k][0], num[j][k] + dp[j - 1][k - 1][0], num[j][k] + dp[j - 1][k + 1][0])  
            dp[j][k][1] = max(num[j][k] + dp[j - 1][k][1], num[j][k] + dp[j - 1][k - 1][1], num[j][k] + dp[j - 1][k + 1][1])  
  
max_result = 0  
min_result = float('INF')  
for l in range(N):  
    if dp[-1][l][1] > max_result:  
        max_result = dp[-1][l][1]  
    if dp[-1][l][0] < min_result:  
        min_result = dp[-1][l][0]  
  
print(max_result, min_result)

 

 

PASS 코드

• 따라서 크기가 3인 1차원 배열을 이용하여
• 입력을 한 줄씩 받으며 그 때 그 때 계산 해주었다.

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))