[BOJ/Python] 2096. 내려가기

📌 문제

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

2096번: 내려가기

 

📌 문제 접근 방법

1. 처음엔 dfs를 사용해서 최소값, 최대값을 갱신시켰는데 숫자가 많아질수록 모든 숫자를 저장하는 자체에서 메모리 초과가 발생하는 것 같았다.
2. 따라서 입력 숫자를 저장하지 않고 입력받자마자 바로 사용할 수 있도록 dp를 사용해서 구현했다.
3. 아래줄의 입장에서 0번째 숫자는 윗줄의 0, 1번째 숫자를 더할 수 있고, 1번째 숫자는 윗줄의 모든 숫자,
   2번째 숫자는 윗줄의 1, 2번째 숫자를 더할 수 있다.
4. 이를 최대, 최소로 나눠서 계속 값을 갱신해줬다.
5. 마지막에 max_sum과 min_sum에 저장된 값 중 최대, 최소값을 출력한다.

 

📌 코드

import sys 
sys.setrecursionlimit(9999999)

def dfs(x, y, sum):
    global min_sum, max_sum
    
    if x == N-1:
        min_sum = min(min_sum, sum)
        max_sum = max(max_sum, sum)
        return

    for dx, dy in dxy:
        nx, ny = x+dx, y+dy

        if 0 <= nx < N and 0 <= ny < 3:
            dfs(nx, ny, sum+number[nx][ny])


N = int(input())
dxy = [(1, -1), (1, 0), (1, 1)]
number = [list(map(int, input().split())) for _ in range(N)]

min_sum = float('inf')
max_sum = 0

dfs(0, 0, number[0][0])
dfs(0, 1, number[0][1])
dfs(0, 2, number[0][2])

print(max_sum, min_sum)

-> 메모리 초과

 

N = int(input())

max_sum = min_sum = list(map(int, input().split()))

for _ in range(N-1):
    input_num = list(map(int, input().split()))

    max_sum = [input_num[0] + max(max_sum[:2]), input_num[1] + max(max_sum), input_num[2] + max(max_sum[1:])]
    min_sum = [input_num[0] + min(min_sum[:2]), input_num[1] + min(min_sum), input_num[2] + min(min_sum[1:])]

print(max(max_sum), min(min_sum))