백준 11066번 문제(파일 합치기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

11066번: 파일 합치기

 

정답 코드는 아래와 같습니다.

import math
 
def solve():
  n = int(input())
  arr = [int(x) for x in input().split()]
  rst = [[0 for _ in range(n)] for _ in range(n)]
  for j in range(1, n):
    for i in range(j-1, -1, -1):
      small = math.inf
      for k in range(j-i):
        small = min(small, rst[i][i+k] + rst[i+k+1][j])
      rst[i][j] = small + sum(arr[i:j+1])
  print(rst[0][n-1])
 
t = int(input())
for _ in range(t):
  solve()

 

먼저 brute force 방식으로 어떻게 이 문제를 해결할 수 있을지 떠올려볼 수 있습니다.

본인이 실제 이런 상황이라고 가정하고 이런 일을 해야한다면 어떻게 처리할 수 있을지 상상해봅니다.

 

n 개의 파일이 있을 때 어느 것이 먼저 합쳐지는게 더 유리한지 잘 모르겠으니,

무작위로 아무거나 선택하고 그것의 오른쪽(또는 왼쪽)에 있는 것과 합치는 방식을 계속 반복한다면

이 문제를 해결할 수 있다는 생각이 듭니다.

 

(제가 떠올린 방식을 아래 영상(풀이)에서는 설명을 좀 잘 못 한거 같습니다.)

 

이 아이디어를 가지고 complexity 를 계산해보겠습니다.

n 개인 상태에서 선택할 수 있는 위치는 n-1개의 지점이 있겠죠. 그리고 그 각각의 경우에 대하여

이제 n-1개인 상태에서 골라야 하므로 선택할 수 있는 위치는 n-2개가 됩니다.

이런식으로 계산하게 되면 복잡도는 O( (n-1)! ) 인 것을 알 수 있습니다.

n 의 최댓값이 500 이기 때문에 이러한 방식으로는 시간 안에 풀리지 않는다는 것을 알 수 있습니다.

 

(풀이 영상에서는 O(n^3) 이라고 잘 못 분석하였습니다. 애초에 영상에서 설명한 방식 자체가 잘 못 되었을 뿐만 아니라, 각각의 경우에 대하여 또 경우가 있기 때문에 서로 곱해야 하는데, 이걸 더하는 바람에 발생한 문제입니다)

 

728x90

 

이런 상황(내가 생각한 풀이 방식이 시간 안에 풀리지 않는 경우)은 알고리즘 문제 풀이에서 정말 자주 맞닥뜨리게 되는 상황이며, 여러가지 방법을 이용하여 시간 안에 계산 가능한 풀이를 떠올릴 수 있습니다.

저는 여기서 작은 경우부터 점차 큰 경우에 대하여 실제로 해보면서 규칙성을 찾아보았습니다.

여기서 중복적으로 발생하는 계산을 발견하였고, 이러한 중복을 없애는 방법으로 자주 사용되는 기법이 DP 임을 떠올렸습니다.

DP 문제를 자주 풀어보신 분들이라면 이 문제가 DP중에서도 2차원 DP라는 것을 어렵지 않게 떠올릴 수 있겠지만, 2차원 DP를 처음 접하는 분들이라면 상당히 낯설게 느껴질 것입니다.

2차원 DP는 어려운 문제이지만 코테에 자주 출제되기 때문에 익숙해질 때까지 연습하시길 권합니다.

 

보통 DP 문제인 것을 알게 되면 정확한 식을 세우려고 노력하는 경우가 종종 있습니다.

정확한 식을 세우기만 하면 사실상 코드는 완성된 것과 다름없기 때문입니다.

1차원인 경우에는 식이 그렇게 어렵지 않지만, 2차원인 경우에는 정확한 식을 세우는 것은 생각보다 어렵습니다.

또한 식을 세우고 재귀적으로 구현하는 경우, 필연적으로 top-down 방식을 이용하게 되어

python 과 같이 함수 호출 depth 에 제약이 비교적 큰 언어에서는 골치아픈 일이 발생하기도 합니다.

따라서 저는 이런 경우에 어떤 방향으로 table 을 채워나가면 정답을 구할 수 있을지 생각합니다.

table 을 채워나간다는 것은 결국 bottom up 방식을 적용하는 것입니다.

어느 방향으로 채워나갈 수 있는지 찾아보니 결국 왼쪽에서 오른쪽으로 채워나가는데,

각 열에서는 아래에서부터 채워나가면 의존성 문제를 해결하면서 채워나갈 수 있음을 알 수 있습니다.

 

(2차원 dp 인데, graph 와 연계되는 문제도 있습니다. 이런 경우에는 사실상 bottom-up 방식으로 구현하기가 상당히 까다롭기 때문에 저도 top-down 방식으로 풉니다.)

 

복잡도를 계산해보면 영상에서는 table 을 다 채우는 것이기 때문에 O(n^2) 라고 했는데요.

각 지점에서 한 줄에 있는 모든 값을 다 더하기도 하고, 가장 작은 값을 찾기도 하므로 사실은 O(n^3) 입니다.

n 이 500 이므로 계산하면 1억이 약간 넘지만, 문제없이 정답 처리 되었습니다.

 

아래 풀이 영상은 위에서 지적한 바와 같이 오류가 많아서 재촬영하려 하였으나,

재촬영하는 것보다 다른 문제의 풀이를 올리는 것이 낫다고 판단하여 재촬영하지 않겠습니다.

많은 양해 바랍니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=4OdIDIYLHlY 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)