[Baekjoon]백준 11066 파일 합치기(골드 3) - C++, Python

문제설명

예제

문제를 살펴보면 파일을 병합하는 과정에서 최소한의 비용이 되도록 하는 경우의 수를 찾아야한다

그래서 동적 계획법 알고리즘이 제일 효율적일것이라 생각하였고, 부분합을 구하는 리스트 하나와

각 구간별 최솟값을 구하기위한 리스트 하나가 있어야한다고 생각하였다

일단, sum[j+1] = sum[j] + tmp와 같은 방식으로 하나의 값을 입력받음과 동시에 구간별 합을 구하도록 작성하였다

이후에 두 개의 for문을 통하여 index를 이동하며 동적 계획법의 결과물 즉, 구간별 최솟값을 갱신한다

첫번째 for문에서는 구해야할 범위를 지정하고 두번째 for문에서는 합치는 범위의 시작 지점을 지정하게 된다

예시를 들어보자면

1 2 3 4 5

와 같은 숫자가 주어져있을때 첫번째 for문의 range가 3이라면 두 번째 for문의 start 지점이 1, 2, 3이 되어

1 2 3, 2 3 4, 3 4 5 와 같은 방식으로 돌아가며 확인을 하게된다

그리고 1 2 3 같은 경우 끝지점은 3이 되게 되는데(3번째 이므로), 이를 기준으로 최솟값을 찾게 된다

sum을 이용하여 구간합을 구해주고 이 값을 이전 구간의 최솟값과 더하게 된다

for(int k = start; k < end; k++) { // 최소 비용 갱신
	sol[start][end] = min(sol[start][end], sol[start][k] + sol[k+1][end] + sum[end] - sum[start-1]);
}

이것을 말로 하기엔 조금 복잡하여 코드와 함께 설명해보자면 k를 start지점부터 한칸씩 이동하며 sol에 최솟값을 

갱신하게 되는데, start부터 end까지의 부분합을 살펴보면서 최솟값을 찾는 과정이다

start 3 4 5 6 end 와 같은 index가 존재할때, start와 3 - end 구간의 부분합이 제일 작은지, start - 3, 4 - end 구간의

부분합이 제일 작은지를 기준점을 이동하여 확인하고 이를 갱신하는 과정이다

이후 sol[start][end]에는 start 지점부터 end지점까지의 최솟값이 저장되게 될 것이다

이를 C++로 구현하면 다음과 같다

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000000000

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int case_num;
    int sum[501] = {0, };
    int sol[501][501] = {0, };
    cin >> case_num;

    for(int i = 0; i < case_num; i++) {
        int file_size;
        cin >> file_size;
        for(int j = 0; j < file_size; j++) {
            int tmp;
            cin >> tmp;
            sum[j+1] = sum[j] + tmp; // 누적 합 구하기 
        }
        for(int range = 1; range < file_size; range++) { // 구해야할 범위
            for(int start = 1; start <= file_size - range; start++) {  // 합치는 범위의 시작 지점
                int end = start + range; // 합치는 범위의 끝 지점
                sol[start][end] = MAX; // 해당 범위(start ~ end)를 합치는데 필요한 최소 비용
                for(int k = start; k < end; k++) { // 최소 비용 갱신
                    sol[start][end] = min(sol[start][end], sol[start][k] + sol[k+1][end] + sum[end] - sum[start-1]);
                }
            }
        }
        cout << sol[1][file_size] << endl;
    }
    

    return 0;
}

사실 처음에는 MAX값을 1e7로 지정하였더니 틀렸습니다가 결과로 출력되었다

그래서 1e9로 설정하였고 정답임을 확인할 수 있었다

같은 로직으로 파이썬 언어로도 작성을 하였는데, 시간초과가 발생하여서 마지막 for문에서 굳이 sum을 한 줄에

처리할 필요가 없다고 판단하였고 그래서 해당 for문의 바깥쪽에도 두어도 시간초과가 발생하였다

블로그를 찾아보아도 해결책을 찾을 수 없어서 PyPy3로 제출하였더니 정답임을 확인할 수 있었다

import sys
input = sys.stdin.readline

case_num = int(input())
for _ in range(case_num):
    file_size = int(input())
    ls = [0]
    tmp = list(map(int, input().split()))
    ls.extend(tmp)
    # print(ls)
    
    sum = [0 for _ in range(file_size+1)]
    for i in range(file_size):
        sum[i+1] = sum[i] + ls[i+1] # 누적 합 구하기 
    # print(sum)
    
    sol = [[0 for _ in range(file_size+1)] for _ in range(file_size+1)]
    for i in range(1, file_size): # 구해야할 범위
        for start in range(1, file_size-i+1): # 합치는 범위의 시작 지점
            end = start + i # 합치는 범위의 끝 지점
            min_file = 1000000000 # 해당 범위(start ~ end)를 합치는데 필요한 최소 비용
            for k in range(start, end):
                min_file = min(min_file, sol[start][k] + sol[k+1][end])
                
            sol[start][end] = min_file + sum[end] - sum[start-1] # 최소 비용 갱신
                
    print(sol[1][file_size])