[백준 11066 파이썬] 파일 합치기 (골드3, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    K = int(input())
    files = [*map(int, input().split())]
    minCost = [[0]*K for _ in range(K)] # 메모이제이션 리스트
    
    # 연속합 (a부터 b까지의 부분연속합을 구할 때, b까지합 - (a-1)까지합 으로 구해주면 됨)
    # 여러번 sum함수 안써도 되고, 딕셔너리 구해두면 O(1) 연산으로 그때그때 부분합 구해서 쓰는게 효율적
    subSum = {-1: 0}
    for idx in range(K):
        subSum[idx] = subSum[idx-1] + files[idx]
    
    for size in range(1, K): # size 크기로 묶은 그룹들의 minCost 구하기
        for start in range(K-1): # 그룹의 시작 인덱스 범위는 0부터 K-2까지
            end = start + size
            
            # 특정 size로 그룹핑했는데 end가 벗어난다면 size 그룹핑 그만두고 다음으로 넘어가기
            if end >= len(files):
                break
            
            result = float("inf")
            # 어떤 구간의 최소비용 minCost는, cut을 기준으로 분할할 때, 좌측 그룹의 최소 비용 + 우측 그룹의 최소 비용 + 좌측 압축 수와 우측 압축 수 더하기
            # 이 때 좌측 압축 수 + 우측 압축 수는 그 구간의 모든 수의 합과 같음
            for cut in range(start, end):
                result = min(result, minCost[start][cut] + minCost[cut+1][end] + subSum[end] - subSum[start-1])
            
            minCost[start][end] = result

    print(minCost[0][-1])

풀이 요약

1. 해당 풀이는 O(N$^3$)이다. C++ 등에서는 AC가 뜨는데, python3에서는 TLE가 뜨고 pypy3으로 제출하면 AC가 뜬다.

   python3으로 통과하기 위해선 크누스 최적화 기법을 적용해야한다. 관심이 있다면 따로 알아보고 적용해서 풀어보도록 하자. 필자는 너무 어렵기도 하고 시간을 너무 잡아먹어서, 학습에 비효율적이라고 판단해서 그냥 DP 풀이로 만족했다...

2. 문제의 조건 중 "연속적으로 파일을 합쳐라"라는 부분을 주의해야한다.

   이 조건에 주의하면서 DP 점화식을 세워보자. 부분 문제를 어떻게 정의해야할까?

   우선 생각해보자. 어떤 방식으로 합쳐나가든, 마지막 이전 단계에서는 합쳐진 숫자 두 개만 남고, 그 두 개를 합치면 완료되게 된다. 따라서,

   "전체 그룹을 두 그룹으로 나눈 뒤, 각 그룹을 최소비용이 되게 압축하면, 압축된 두 수를 더한 값과 두 그룹의 최소비용의 합이 분할 이전 전체 그룹의 최소비용이다"

   이런 아이디어를 떠올릴 수 있다.

   점화식스럽게 다시 표현하자면

   "전체 그룹의 압축 최소비용 = 두 그룹으로 분할하고, 각 그룹의 압축 최소비용의 합 + 압축 완료된 두 숫자의 합"
   
   

3. 딱 봐도 재귀의 구조가 보인다. 재귀 구조에 메모이제이션을 활용한 DP로 풀 수 있겠다는 생각이 든다.

4. 이제 본격적으로 구현을 해보자.

   K = 소설 파일 수
   files = 입력받는 파일 크기들 리스트
   minCost = 2차원 리스트이다. minCost[a][b]는 files의 인덱스 a부터 b까지(b 포함)에 해당하는 하나의 그룹의 압축 최소비용을 의미한다.
   subSum = 딕셔너리이다. files의 어떤 idx까지의 연속합

5. 우선 subSum을 채워주자. key : -1부터 K-1까지 채워주면 된다. subSum[n]은 files의 idx 0부터 n까지의 연속합을 의미한다. 이 딕셔너리는 나중에 그룹의 연속합을 구할 때 사용할 것이다.

6. top-down 방식이 아닌 bottom-up 방식으로 풀 것이다. 재귀 방식으로 푸니 pypy3으로도 TLE가 난다.

   전체적인 흐름대로 설명하겠다.

   1) 길이가 size인, 만들 수 있는 모든 그룹들에 대해 압축 최소비용을 구하고 minCost(DP리스트)에 저장해나갈 것이다. 가장 바깥 for문이다.

   2) 각 길이 size에 대해, 만들 수 있는 모든 그룹들의 경우의 수를 for문으로 돌 것이다. 이를 위해 size for문을 돌면서 특정 size마다 start를 0부터 K-2까지 돌 것이다. end는 자연스레 start + size로 정해진다. 이 것이 특정 size에 대해 가능한 모든 그룹을 순회하는 for문이다. start는 그룹의 시작 인덱스, end는 그룹의 끝 인덱스를 의미한다.(여기서 인덱스란 files에서의 인덱스를 말하는 것임) 두번째 for문이다.

   3) start가 k-2까지인 이유는, size가 가장 작은 1일 때를 생각해보면, start가 만약 k-1일때 end는 start + size = k임. end가 files를 넘어가버렸으니 이 경우는 생각할 필요가 없음.

   4) 만약 end가 files를 벗어나면(>=len(files)) 두번째 for문을 벗어나주면 된다. 이 때는 특정 size에 대해 가능한 모든 그룹을 다 순회했다는 뜻이기 때문이다.

   5) result에 아주 큰 수 float("inf")를 넣어놓고, 현재 그룹의 압축 최소비용을 구하자. 세번째 for문이다.

   6) 아까 설명한 원리대로 점화식을 생각해보면

   minCost[start][end] = min(minCost[start][cut] + minCost[cut+1][end] + subSum[end] - subSum[start-1] for cut in range(start, end))

   
   

   sudo 코드니까 의미만 파악하자.

   예를 들어 생각해보자. minCost[3][7]을 두 그룹으로 분할하면 minCost[3][3]와 minCost[4][7], minCost[3][4]와 minCost[5][7], ..., minCost[3][6]와 minCost[7][7]로 나눌 수 있다. 이게 바로 세번째 for문인 for cut in range(start, end)가 의미하는 바이다.

   여기서 minCost[3][7]을 minCost[3][4], minCost[5][7]로 분할한 경우가 최소 압축비용이라고 가정해보자.(실제론 아닐 수도 있음 가정만 하자)

   이 때 minCost[3][7] = minCost[3][4] + minCost[5][7] + subSum[end] - subSum[start-1] 이다.

   이 식은 직접 그룹 원소를 일일히 적어가면서 따라가보면 금방 이해될 것이다. 두 그룹으로 분할했을 때, 두 그룹의 압축 최소비용을 일단 더한다. 그러나 여기서 끝이 아니다. 두 그룹이 압축이 끝나고나서 두 개의 압축된 수가 남아있을텐데, 이 두 수의 합도 마저 더해줘야 그 것이 전체 그룹의 압축 최소비용이 된다. 그런데 어떤 그룹의 압축 결과 수는 그 그룹의 모든 수를 더한 것과 같다. 즉, 두 그룹의 압축 수를 더한 값은 결국 단순히 전체 그룹의 모든 수를 더한 값과 같다. 예를 들어 [30, 20, 15]를 압축하면 65로 압축되는데, 이 값은 단순히 그룹의 수를 모두 더한 30+20+15이다.

   그러므로, 아까 딕셔너리에 0부터 idx까지의 연속합을 다 구해놨으니, 이걸 이용해서 전체 그룹의 연속합을 구하면 된다.

   이걸 세번째 for를 돌면서 반복하면서 result에 최소를 계속 갱신해서 압축 최소비용을 구하는 것이다.

   이제 전체 그룹의 압축 최소비용인 minCost[0][-1]을 출력하면 끝!

7. 3중 for문이므로 시간복잡도는 O(N$^3$)이다.

배운 점, 어려웠던 점

• 아.. 너무 어려웠다... 시간을 너무 많이 잡아먹었다!!

• 다른 사람 풀이 참고 후, 내가 문제 이해부터 잘못했다는 것을 알게 됐다. 파일을 "연속"적으로 합쳐야하는데, 이걸 놓치고 막 건너뛰어서 파일을 합치는 등 삽질 겁나 했다...

• 놓친 조건을 파악한 뒤 DP로 풀어봤다. 구간 분할을 양 끝 인덱스 start, end로 구현하는 아이디어는 생각해냈음

• 구간의 길이가 1일 때는 압축 자체를 안하니까 비용이 0인데, 이걸 잘못 생각해서 삽질을 했다. (그 인덱스의 files값을 인덱싱해서 minCost에 넣었음...)

• 전체 그룹의 minCost는, 분할한 두 그룹의 minCost를 더한 것에서 끝나는게 아니라, 각 그룹의 압축하고 난 결과값을 더한 값도 더해줘야 함을 생각하지 못했음.

• float("inf")에 대해 배웠다. 어떠한 수보다도 큰 수로 취급된다고 한다. 반드시 float 자료형만 가능하다. 음의 무한대는 -float("inf")를 쓰면 된다. 이 문제에서는 최솟값을 계속 갱신하는데에 썼다.

• subSum 딕셔너리에 연속합을 미리 구해놓고 나중에 특정 그룹의 연속합을 구할 때 인덱싱함으로써, sum 함수를 중복되게 여러번 반복하는 경우를 피해 시간복잡도를 줄이는 아이디어를 배웠다.

• python3으로 AC를 받기 위해서는 크누스 최적화를 적용해야한다는데... 너무 어렵기도하고 시간을 너무 잡아먹어서 학습에 비효율적이라 생각해서 그냥 생략했다.

• 이 풀이보다 시간복잡도를 절반가량 줄일 수 있는, pypy3 AC 받는 또 다른 풀이가 있었는데 아무리 봐도 이해가 안되어서 그냥 넘어갔다... 많은 문제를 풀고난 뒤 나중에 다시 한 번 해봐야겠다.