백준 11066 파일 합치기

문제링크 : https://www.acmicpc.net/problem/11066

문제 추상화

• 연속해있는 값들을 두개씩 합칠 때마다 각 값을 더한 비용이 생긴다
• 모든 값을 하나로 합칠때, 최소의 비용을 구하기

아이디어

• 모든 경우의 수를 확인 가능?
  • 경우의 수 : 각 위치에서 앞의 것과 합칠떄, 그리고 합치지 않을때를 각각 계산
  • 그럼 중간에 하나씩 떨어져 있는 것을 계산이 불가
• DP 사용
  • 개념이 복잡해서 헷갈릴수 있는데 천천히 읽어보자.
  • DP[x][y] : x부터 y까지 더할때 최소값
  • DP[x][y] = min(DP[x][z] + DP[z+1][y]) + sum(x~y)
  • 3중 루프를 돌아야하는데
    • y-x 값 기준
    • 시작값 x
    • 중간에 끊는 z값을 기준
  • 즉, 3중루프가 다음처럼 구현됨
    • 일단, dp[1][2], dp[2][3], dp[3][4] ... 구하고
    • dp[1][3] = dp[1][2] + dp[2][3], dp[2][4] = dp[2][3] + dp[3][4], ...
    • dp[1][4] = min(dp[1][2] + dp[2][4], dp[1][3] + dp[3][4]) ...
      • 이걸 시험 중 생각해낼 수 있을까? > 불가능
  • 문제 유형을 외우자

시간복잡도 계산

• O(T * K^3) : T * 1.25e8

인트 계산

• DP 최대값 : 모든 숫자가 K번 더해질경우 : 10000 * 500 * 500 = 25e8 > INT 불가, LL 사용

코드(C++)

#include <iostream>
 
using namespace std;
typedef long long ll;
 
const ll inf  = 2.6e9;
ll dp[510][510];
int sum[510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(&dp[0][0], &dp[509][510], 0);
        fill(sum, sum+510, 0);
        
        int K; cin >> K;
        
        // 합을 추후 계산해야해서 미리 구함
        for(int i=1; i<=K; i++) {
            int ei; cin >> ei;
            sum[i] = sum[i-1] + ei;
        }
        
        for(int d=1; d<K; d++) {
            for(int st=1; st+d<=K; st++) {
                int en = st+d;
                
                // 초기값 무한대로 설정
                dp[st][en] = inf;
                for(int mid = st; mid<en; mid++) {
                    dp[st][en] = min(dp[st][en], dp[st][mid] + dp[mid+1][en] + sum[en]-sum[st-1]);
                }
                
            }
        }
        
        cout << dp[1][K] << '\n';
        
    }
    return 0;
}
 

문제유형

• DP - 연속한 값끼리 더해서 최소값구하기
  • 일반적 DP 사용할 경우, 중간에 홀로 떨어지는 값 발생
  • DP[st][en] : st부터 en까지의 최소값
  • DP[st][en] = min(DP[x][z] + DP[z+1][en]) + sum(st~en)
  • 3중루프가 다음처럼 구현됨
    • 일단, dp[1][2], dp[2][3], dp[3][4] ... 구하고
    • dp[1][3] = dp[1][2] + dp[2][3], dp[2][4] = dp[2][3] + dp[3][4], …
    • dp[1][4] = min(dp[1][2] + dp[2][4], dp[1][3] + dp[3][4]) ..