[백준] 2096: 내려가기 (DP, 파이썬)

📌 문제 조건

- 메모리 제한 4MB

 

📌 구해야 하는 정답

   N x 3 칸에 0~9의 숫자가 적혀있다. 

   첫 줄부터 마지막 줄까지 내려가면서 얻는 최대 점수와 최소 점수를 모두 구해야한다. 

   위 그림의 조건을 만족하면서 내려가야한다. 

📌 풀이 하기

1. DP 테이블 정의하기 

• D = [[0, 0, 0], ... , [0, 0, 0]]로 정의한다면  N X 3크기의 공간을 차지하므로 현재 상태와 이전 상태를 저장하는 리스트만 있어도 충분하다. D[i]는 i번째 줄에서의 최대 점수의 합이다. 

• 최대 값을 구하는 점화식은 다음과 같다. -> dp테이블이 공간을 잡아먹으므로 다른 방법을 사용한다 
  • D[i][0] = max(D[i - 1][0], D[i - 1][1]) + S[i][0]
  • D[i][1] = max(D[i - 1]) + S[i][1]
  • D[i][2] = max(D[i - 1][1], D[i - 1][2]) + S[i][2]
• DP 테이블 크기를 줄인 점화식은 아래와 같다

cur_max[0] = max(prev_max[0], prev_max[1]) + S[0]
cur_max[1] = max(prev_max) + S[1]
cur_max[2] = max(prev_max[1], prev_max[2]) + S[2]

 

📌 코드 설계하기

1. 입력 받는 첫 줄을 prev_max로 저장한다.
2. 다음 입력 받는 줄을 curr_max로 저장한다.
3. curr_max[0], curr_max[1], curr_max[2]에 대해 점화식을 적용한다. 
4. min에도 max와 같은 방법을 적용한다.

📌 시도 회차 수정 사항

• Q[0][0], Q[0][1], Q[0][2] = S[0][0], S[0][1], S[0][2] 는 반복문 밖에서 한 번만 초기화해야했다. 잘못된 위치에서 초기화 했다. 
• 아래와 같이 코드를 짰더니 시간 초과가 떴다.
  • DP_MAX와 DP_MIN 함수는 각 행의 값들과 이전 행에서 계산된 결과에 의존하므로 전체 행렬을 저장할 필요 없이, 현재 행과 이전 행만 유지하면 된다.

import sys
input = sys.stdin.readline

N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int, input().split())))

D = list([0] * 3 for _ in range(N))
Q = list([0] * 3 for _ in range(N))
def dp_max(D):
    for i in range(1, N):
        D[0][0], D[0][1], D[0][2] = S[0][0], S[0][1], S[0][2]
        D[i][0] = max(D[i - 1][0], D[i - 1][1]) + S[i][0]
        D[i][1] = max(D[i - 1]) + S[i][1]
        D[i][2] = max(D[i - 1][1], D[i - 1][2]) + S[i][2]
    return max(D[N - 1][0], D[N - 1][1], D[N - 1][2])

def dp_min(Q):
    for i in range(1, N):
        Q[0][0], Q[0][1], Q[0][2] = S[0][0], S[0][1], S[0][2]
        Q[i][0] = min(Q[i - 1][0], Q[i - 1][1]) + S[i][0]
        Q[i][1] = min(Q[i - 1]) + S[i][1]
        Q[i][2] = min(Q[i - 1][1], Q[i - 1][2]) + S[i][2]
    return min(Q[N - 1][0], Q[N - 1][1], Q[N - 1][2])

print(dp_max(D), dp_min(Q))

 

 

📌 정답 코드

import sys
sys.stdin = open('../input.txt')
input = sys.stdin.readline

N = int(input())
cur_max = [0] * 3
prev_max = list(map(int, input().split()))
cur_min = [0] * 3
prev_min = prev_max[:]

for _ in range(1, N):
    S = list(map(int, input().split()))
    cur_max[0] = max(prev_max[0], prev_max[1]) + S[0]
    cur_max[1] = max(prev_max) + S[1]
    cur_max[2] = max(prev_max[1], prev_max[2]) + S[2]

    cur_min[0] = min(prev_min[0], prev_min[1]) + S[0]
    cur_min[1] = min(prev_min) + S[1]
    cur_min[2] = min(prev_min[1], prev_min[2]) + S[2]

    prev_max = cur_max[:]
    prev_min = cur_min[:]

print(max(prev_max), min(prev_min))