백준 11066번 _ 파일 합치기

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

11066번: 파일 합치기

 주의사항

 소설이므로 장이 섞이면 안된다. -> 그러므로 바로 옆에 있는것하고만 파일을 합칠수있다!

---

 접근

 총 파일이 4개라고 하면 파일이 합쳐지는 경우의 수는

 ( (1, 2) (3, 4) ) , ( ( 1, (2, 3) ), 4), .....등등등 여러가지방법이 나오게 된다.

 이를 하나하나 해보기에는 너무나도 많은 겹치는 연산들이 있을것이다. 그렇다면 이 겹치는 연산을 줄이기 위해서는 동적계획법을 이용하는게 적절해 보인다.

---

 풀이방법

 일단 dp[start][end]는 start부터 end까지 합쳐지는데 최솟값이다.

 

 점화식을 세워보면

 dp[i][j] = dp[i][mid] + dp[mid+1][j] + (i~j까지의 부분합)이다.

 그리고 이를 3중 for문을 이용해서 풀면 답이 나온다.

 

 1번째 for문 : gap

 2번째 for문 : start 

 3번째 for문 : mid -> start <=mid < end ( mid < end인 이유는 mid+1로 자르기 때문 )

---

 간단한 예시동작  

 아마 위의 글만 읽어서는 와닿지 않을 것이다. 간단한 예시를 들어보겠다.

 

 ex) 총 4장, 순서대로 40, 30, 30, 50

 

 

 

 

 여기까지 하게되면 dp[1][4]가 정답이다.

---

 전체코드

#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;

int dp[501][501];
int cost[501];
int sum[501];

int main()
{
	int testcase;
	cin >> testcase;
	for (int t = 0; t < testcase; t++)
	{
		int k;
		cin >> k;

		//make cost
		for (int i = 1; i <= k; i++)
		{
			cin >> cost[i];
		}

		//make sum
		for (int i = 1; i <= k; i++)
		{
			if (i == 1)
				sum[i] = cost[i];
			else
				sum[i] = sum[i - 1] + cost[i];
		}

		//solve
		for (int gap = 1; gap < k; gap++)
		{
			for (int start = 1; start + gap <= k; start++)
			{
				int end = start + gap;

				dp[start][end] = INT_MAX;

				for (int mid = start; mid < end; mid++)
				{
					dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start-1]);
				}
			}
		}
		cout << dp[1][k] << endl;

		/*for (int i = 1; i <= k; i++)
		{
			for (int j = 1; j <= k; j++)
			{
				cout << dp[i][j] << ' ';
			}
			cout << endl;
		}*/
	}
	return 0;
}

---

 후기

 "난 진짜 재능이 없구나ㅠ.." 풀면서 이 생각만 났다. 뭔 답을 읽어도 뭔 소리진지 당최 모르겠어서 눈물이 찔끔났다. 

 

 결국 답을 보고 겨우겨우 이해해서 풀기는 했지만, 접근방식이나 dp에 대한 이해도, 전체적인 실력이 모두 삼위일체로 허접이라는것을 다시한번 깨닫게 해주는 문제였다. 종만북 dp파트도 진도가 안나가는 이유가 있었다.ㅋㅋㅋㅋㅋㅋ

 

 이번년도 안에 코드포스 블루.. 갈수있을까?