[백준] No.11066 - 파일 합치기 (C++, DP)

문제

 

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

11066번: 파일 합치기

 

풀이

 

solved.ac 난이도: Gold 3

 

 

연속된 순서의 파일끼리만 합쳐야 한다는 조건이 없다면 우선순위 큐로 간단히 풀 수 있지만, 연속된 파일끼리 합치기 위해 다이나믹 프로그래밍(DP)를 사용해야 한다.

 

dp[start][end]를 start ~ end까지의 파일을 연속되게 합칠 때(하나의 임시 파일로 만들 때) 최소 비용이라고 하자.

이를 구하기 위해서는 start~end 파일들을 두 가지의 임시파일(A와 B)로 나누어 주어야 한다.

 

이때 만들 수 있는 임시파일의 종류는 다음과 같다.

1. A: start / B: start + 1 ~ end

2. A: start ~ start +1 / B: start + 2 ~ end

3. A: start ~ start +2 / B: start + 3 ~ end

...

(end - start). A: start ~ end - 1 / B: end

 

따라서 dp[start][end]를 구하기 위해서 start~end를 두 집합(start~idx와 idx+1 ~ end)으로 나누어 다시 재귀 호출을 통해 구할 수 있다.

 

int dp[501][501];
int arr_sum[501];
 
int MinCostDFS(int start, int end){
  if(start == end)
    return files_size[start];
    
  int& ret = dp[start][end];
  if(ret != -1)
    return ret;
  
  ret = INF;
  for(int idx = start; idx< end ; ++idx)
    ret = min(ret, MinCostDFS(start, idx) + MinCostDFS(idx+1, end));
  
  //구한 값에 이번 파일의 크기 더해주기
  ret += arr_sum[end] - arr_sum[start -1];
  return ret;  
}

 

단, 추가적으로 dp[start][end]에는 두 임시파일을 합치는데 드는 비용인 A와 B의 임시 파일의 크기(start ~ end까지의 파일을 합한 값)가 필요하다.

따라서 연속된 값들의 합을 빠르게 구할 수 있는 연속 합 기법을 사용하였다.

 

 

코드