https://www.acmicpc.net/problem/11066
Reference:
https://velog.io/@leeinae
https://galid1.tistory.com/
문제
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.
예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.
소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
알고리즘 풀이에 대해서 DP에 대한 이해가 부족한 것 같다. 그동안 풀어본 문제에서 활용한 것들 통해서 풀이해보려고 했지만 실패해서 해당 블로그글을 중심으로 참조해서 공부해봤다.
Dynamic Programming
우선 DP( Dynamic Programming )은 동적 프로그래밍으로, 큰 문제를 작은 문제 하나하나로 나누어서 풀이해 나가는 방식이다. 작은 문제들은 같은 입력 하에 항상 같은 출력이 나오는 문제로, 반복해서 일어난다.
피보나치 수열과 같이 , 수열의 최종값을 큰 문제라고 하면, 그림에서 상자들은 작은 문제라고 볼 수 있다. 최종값을 구하려면 작은 상자들의 값이 계속해서 사용된다.
1 = 0 +1 이고, 2 = 1 + 1 , 3 = 2 + 1, 각 상자를 배열이라고 보면 dp 배열의 요소들이 다음 요소를 구하는 데에 계속해서 물고 물려서 사용된다는 뜻이다. dp 배열 요소들은 각각이 정답이지만, 다음 정답을 찾기위한 수단이 되기도 하는 것이다.
leeinae님의 답안을 분석해보면서 dp를 더 상세히 알아봤다.
가장 먼저 변수를 선언하는 과정이다.
1 2 3 4 5 6 7 8 9 10 11 12 | int[][] dp = new int[file.length][file.length]; int[] sum = new int[file.length]; sum[0] = file[0]; for (int i = 1; i < sum.length; i++) { sum[i] = sum[i-1] + file[i]; } for (int i = 0; i < file.length -1; i++) { dp[i][i+1] = file[i] + file[i+1]; } | cs |
dp를 소설의 장수X장수 크기의 int배열의 배열로 선언하고, sum을 int배열로 선언해서, sum에 각 장수별 페이지의 누적합을 입력하고, dp[i][j]에는 i번째 장부터 j번째 장까지 합치는 비용이 들어가기 때문에, 우선적으로 바로 다음장과 합치는 비용을 먼저 입력한다.
1 2 3 4 5 6 7 8 9 10 11 | for (int j = 2; j < file.length; j++) { //열 for (int i = 0; i+j < file.length; i++) { //행 for (int k = i; k < i + j; k++) { if (dp[i][i + j] == 0) { dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + sumDist(sum, i, i + j); } else { dp[i][i + j] = Math.min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + sumDist(sum, i, i + j)); } } } } | cs |
1 2 3 4 5 6 7 | static int sumDist(int[] sum, int start, int end) { if (start == 0) { return sum[end]; } else { return sum[end] - sum[start - 1]; } } | cs |
노트에 정리해본 dp[i][j]를 구하는 과정이다. sumDist를 이용해 해당 장들의 페이지 총 합을 더해주고, 이것은 dp[i][i+j]가 0인 경우, 즉 아직 입력되지 않은 경우에 해당하고, 입력이 돼있는 경우는 해당 값과 위 계산값 중 작은 값을 선택해 입력한다.
이런식으로, 3개의 for문 사이에서 시작 장인 i, 목표 장인 j, 중간에 껴있는 장들 중 임의추출한 k의 모든 경우의 수를 찾아내 dp의 논리가 구현된다.
원하는 큰 문제의 답인 dp[0][n]의 값은 dp[0][1],dp[1][2],‥‥dp[n-1][n-2] 들을 통해 dp[0][2],dp[1][3],‥‥ 들을 구하고, 그를 통해 다시 dp[0][3],dp[1][4] 들을 통해서 구해야한다. 시작 장과 목표 장과의 차이 j, 시작장 i 를 for문을 통해 순회하도록, 그에 해당하는 dp값을 k값의 반복을 통해 차례차례 구하는 것이다.
