[baekjoon] 백준 2096번(파이썬): 내려가기

문제

2096번: 내려가기

알고리즘

- 반복문을 통해 각 줄을 확인한다.

- 반복문을 통해 각 칸의 들어갈 수 있는 최대/최소 값을 구한다.

- 최대/최소 값은 매 반복이 끝날 때마다 max_dp/min_dp에 초기화시켜준다.

코드

import sys

n = int(sys.stdin.readline())
max_dp = [0 for _ in range(3)]
min_dp = [0 for _ in range(3)]
max_tmp = [0 for _ in range(3)]
min_tmp = [0 for _ in range(3)]

# 반복문을 통해 각 줄을 확인
for i in range(n):
    a, b, c = map(int, sys.stdin.readline().split()) # 3칸의 수

    # 반복문을 통해 각 칸의 들어갈 수 있는 최대/최소 값을 구한다.
    for j in range(3):
        if j == 0:
            max_tmp[j] = max(max_dp[j], max_dp[j + 1]) + a
            min_tmp[j] = min(min_dp[j], min_dp[j + 1]) + a

        elif j == 1:
            max_tmp[j] = max(max_dp[j], max_dp[j - 1], max_dp[j + 1]) + b
            min_tmp[j] = min(min_dp[j], min_dp[j - 1], min_dp[j + 1]) + b

        else:
            max_tmp[j] = max(max_dp[j], max_dp[j - 1]) + c
            min_tmp[j] = min(min_dp[j], min_dp[j - 1]) + c

    # 각 칸의 들어갈 수 있는 최대/최소 값을 max_dp/min_dp에 초기화
    for j in range(3):
        max_dp[j] = max_tmp[j]
        min_dp[j] = min_tmp[j]


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

 

메모리 초과..

import sys

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
max_dp = [[0 for _ in range(3)] for _ in range(n)]
min_dp = [[0 for _ in range(3)] for _ in range(n)]

for i in range(n):
    for j in range(3):
        if j == 0:
            max_dp[i][j] += max(max_dp[i - 1][j], max_dp[i - 1][j + 1])
            min_dp[i][j] += min(min_dp[i - 1][j], min_dp[i - 1][j + 1])

        elif j == 1:
            max_dp[i][j] += max(max_dp[i - 1][j], max_dp[i - 1][j - 1], max_dp[i - 1][j + 1])
            min_dp[i][j] += min(min_dp[i - 1][j], min_dp[i - 1][j - 1], min_dp[i - 1][j + 1])

        elif j == 2:
            max_dp[i][j] += max(max_dp[i - 1][j], max_dp[i - 1][j - 1])
            min_dp[i][j] += min(min_dp[i - 1][j], min_dp[i - 1][j - 1])

        max_dp[i][j] += graph[i][j]
        min_dp[i][j] += graph[i][j]


print(max(max_dp[2]), min(min_dp[2]))

배열을 많이 사용해서 메모리 초과가 뜬 것으로 확인된다.

이를 해결하기 위해서 세 개의 변수에 각 칸의 수의 최대/최소 값을 기억한 후 출력했다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법