https://www.acmicpc.net/problem/11066
거의 일주일동안 푼 문제, 답을 봐도 뭔소린지 모르겠어서 멘탈이 터졌다.
문제
소설가인 김대전은 소설을 여러 장(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 이다.
소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
입력
프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.
출력
프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.
예제 입력 1
2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32
예제 출력 1
300
864
코드는 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <iostream> #define min(a,b) (((a) < (b)) ? (a) : (b)) long long dp[501][501]; long long sum[501]; int T, K; int main() { std::cin >> T; for (int testCase = 0; testCase < T; ++testCase) { std::cin >> K; for (int i = 1; i <= K; ++i) { std::cin >> sum[i]; sum[i] += sum[i - 1]; } for (int x = 2; x <= K; ++x) for (int y = 1; y + x - 1 <= K; ++y) { dp[y][x + y - 1] = 2147483647; for (int m = y + 1; m - y < x; ++m) dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]); } std::cout << dp[1][K] << '\n'; for (int y = 0; y <= K + 2; ++y) { for (int x = 0; x <= K + 2; ++x) { std::cout.width(3); std::cout << dp[y][x] << ' '; } std::cout << '\n'; } } return 0; } | cs |
예제 1의 설명으로는 좀 애매한 부분이 있어서.. 예제 2의 동작원리를 보게 되었다.
행렬은 이러한 숫자들로 구성이 되어 있는데,
3중 반복문이 어떻게 동작하는지 살펴봐야 한다.
1 2 3 4 5 6 7 | for (int x = 2; x <= K; ++x) for (int y = 1; y + x - 1 <= K; ++y) { dp[y][x + y - 1] = 2147483647; for (int m = y + 1; m - y < x; ++m) dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]); } | cs |
행렬은 x좌표가 2에서 시작한다. y는 x좌표의 값을 더해(-1도 추가) 입력받은 K장까지 증가하게 된다. int y = 1; y + x - 1 <= K; ++y
y는 1부터 15까지 모든 행을 다 순회하기 때문에 1에서 시작한다. y + x - 1 <= K인 이유는 y <= K일 경우에 행렬 오버플로가 발생하기 때문
m은 양옆의 원소들을 비교하기 위해 존재하는 반복문이다. 자세한 동작은 계속 설명하면서 다시 보자.
첫번째 반복의 상황에선 x = 2, y = 1일 때, m = y + 1이 2, 즉 1 < 2(m - y < x) 이기 때문에 x = 2, y = 1, m = y + 1 일 때
dp[y][x + y - 1]이 2147483647(INT_MAX)이고,
min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1])
=
dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]
dp[2][2] + dp[1][1] + sum[2] - sum[0]
0 + 0 + 22(sum[2]) - 0(sum[0])
이기 때문에 22가 들어가게 되는 것이다.
y가 2일 때는 25(sum[x + y - 1] = sum[3]) - 1(sum[y - 1] = sum[1]) 이다.
즉,
dp[3][3] + dp[2][2] + sum[3] - sum[1] = 24이다.
아직까진 반복문 m이 한번밖에 돌지 않는다. 또한 동작도 납득할 수 있는 수준이다.
이제 x = 3 일 때, y가 어떻게 동작하는지 알아야 한다.
for (int m = y + 1; m - y < x; ++m)이다. 즉 m = 2일때, m - y < x(2 - 1 < 2), 반복문은 두번 반복된다.
m = 2 일 때,
y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[2][3] + dp[1][2](0 + 24) 이다.
dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]
즉, 24 + 25 = 49 이다. dp[y][x + y - 1]는 49이다.
m = 3 일 때,
y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[3][3] + dp[1][1](22 + 0) 이다.
dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]
즉, 22 + 25 = 47 이다. 49 > 47 이기 때문에 dp[y][x + y - 1]는 47이다.
혼란스러운 머리를 부여잡고 여기까지 따라왔다면 이것 또한 이해할수있따
dp[1][4]는 (22 + 7) + (1 + 21 + 3 + 4) = 58 이고,
dp[2][5]는 (19 + 0) + (21 + 3 + 4 + 5) = 52 이다.
사진상의 행렬 비교 순서는 m = 2 일 때,
(35 + 0) + (1 + 21 + 3 + 4)
(7 + 22) + (1 + 21 + 3 + 4)
(0 + 47) + (1 + 21 + 3 + 4)
이 중 가장 작은것은 58이기 때문에, dp[1][4]는 58이 들어가는 것
같은 원리다. 계산은 이와 같은 로직으로 돌아가게 된다.
어째서 이러한 동작을 하게 되냐면,
잘 모르겠다ㅎ 대충 이분해서 최솟값을 계산하는 것은 얼추 알 것 같다. 설명할 자신은 없지만
첫 번째 사진은 1, 21 ~ 32 중 최소 비용을 쓴 크기 (839 + 0) + sum[15]
두 번째 사진은 1 ~ 21, 3 ~ 32 중 최소 비용을 쓴 크기 (739 + 22) + sum[15]
...
n 번째 사진은 1 ~ 35, 5 ~ 32 중 최소 비용을 쓴 크기 (515 + 144) + sum[15]
515 : 1 ~ 35 중 최소 비용
144 : 5 ~ 32 중 최소 비용
... K번까지 돌아가는 것이다.
그냥 그러려니 하고 암기하자...
'알고리즘' 카테고리의 다른 글
2. C++언어 역사 개요..? (0) | 2019.10.07 |
---|---|
1. 희망의 나라로 알고리즘 (0) | 2019.10.07 |
백준 1912: 연속합(DP) (0) | 2019.08.27 |
백준 9251: LCS(DP) (0) | 2019.08.26 |
백준 2565: 전깃줄(DP) (0) | 2019.08.23 |