2096

날짜 : 2023. 10. 17

사용 언어 : python

 

문제

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

 

 

코드

import sys
import copy

n = int(sys.stdin.readline())
graph = list()
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

dp_max = copy.deepcopy(graph[0])
dp_min = copy.deepcopy(graph[0])

# print(dp_max, dp_min)
maxt = list()
mint = list()
for i in range(1, n):
    maxt = copy.deepcopy(dp_max)  # 앞줄까지의 dp
    mint = copy.deepcopy(dp_min)
    for j in range(3):
        if j == 0:
            dp_max[j] = max(graph[i][j] + maxt[0], graph[i][j] + maxt[1])
            dp_min[j] = min(graph[i][j] + mint[0], graph[i][j] + mint[1])
        elif j == 1:
            dp_max[j] = max(graph[i][j] + maxt[0], graph[i][j] + maxt[1], graph[i][j] + maxt[2])
            dp_min[j] = min(graph[i][j] + mint[0], graph[i][j] + mint[1], graph[i][j] + mint[2])
        else:  # j가 2
            dp_max[j] = max(graph[i][j] + maxt[2], graph[i][j] + maxt[1])
            dp_min[j] = min(graph[i][j] + mint[2], graph[i][j] + mint[1])
    # print(dp_max)
print(max(dp_max), min(dp_min))

 

 

풀이

- 위의 풀이처럼 인덱스가 0, 1, 2인 경우에 따라서 DP를 활용해 최대값, 최소값을 갱신하고, 가장 마지막 row의 최대값, 최소값을 출력한다.

- 다만 메모리 크기가 정해져 있기 때문에 n * 3의 메모리를 선언하지 않고, 1 * 3의 리스트 2개를 선언한 다음, 앞선 DP들을 저장할 리스트(maxt, mint)들을 뽑아내면서 값들을 갱신해 나간다.

 

 

알게된 점

- 그냥 두 개의 n * 3 크기의 리스트 2개를 선언해서 풀었더니 곧바로 풀렸다.

- 그런데 당연히 메모리 초과가 발생했고, 2차원 배열을 만들어서 갱신하는 방식으로 풀어보려고 했지만 계속 max 부분에서 이상한 값이 나왔다.

- 하루를 꼬박 디버깅해보니 가장 앞부분에서 max_dp, min_dp = graph[0], graph[0] 방식으로 선언을 했었다.

- 이렇게 하는 바람에 당연히 max_dp와 min_dp, graph는 서로 연결되고, 자연스럽게 값에 영향을 미치게 된다.

- 그래서 이 부분을 각각 deepcopy 방식으로 선언했고 문제는 바로 풀렸다.

- 이런 슬라이딩 윈도우 문제에서는 선언방식을 되게 조심해야겠다. 너무 많은 시간을 허비했다...

 

 

참고 사이트

-