[백준 10427] 빚 (C++)

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

 

문제

---

민균이에게는 ‘빚쟁이’ 라는 별명이 있다. 이 별명은 악덕 사채업을 하는 김우현연구소에서 민균이가 빌린돈을 잘 갚지 않는다고 하여 붙여준 이름이다. 

민균이가 최근 N (1 ≤ N ≤ 4000) 번 돈을 빌렸고, 그때마다 빌린 돈이 각각 A(1), A(2), …, A(N) (1 ≤ A(i) ≤ 10⁴) 라고 하자. 악덕 사채업소 김우현 연구소는 이름만큼이나 빌린 돈을 갚는 방식이 독특하다.

먼저, 김우현 연구소가 민균이에게 M번 (1 ≤ M ≤ N) 의 빚을 갚으라고 명령하면, 민균이는 N번중 아무렇게나 M 번을 고르고, 고른 것 중에서 가장 많은 돈을 빌렸을 때 빌린돈 x M 을 갚아야 한다. 이렇게 하면 민균이가 김우현 연구소에 갚아야 하는 돈은 (빌린돈 + 추가적으로 더 갚아야 할 돈) 이 된다. 예를 들어, 민균이가 3번 돈을 빌렸고, 각각 2, 5, 3 의 돈을 빌린 경우, 김우현 연구소가 2번의 빚을 갚으라고 명령하면, 민균이가 첫 번째, 두 번째를 선택했을 경우 갚아야 하는 돈은 5 x 2 = 10 이 되고, 추가적으로 더 갚아야 할 돈은 10 – (2 + 5) = 3 이 된다. 만약 민균이가 첫 번째, 세 번째를 선택하면, 갚아야 하는 돈은 3 x 2 = 6 이 되고, 추가적으로 더 갚아야 할 돈은 6 – (2 + 3) = 1 이 된다. 

민균이는 이런 김우현 연구소가 괘씸하여 어떻게든 추가적으로 더 갚아야 할 돈을 최소한으로 하고 싶어 한다. S(M) 을 김우현 연구소가 민균이에게 M번의 빚을 갚으라고 명령했을 때 민균이가 M 번을 선택하여 추가적으로 갚아야 하는 돈의 최솟값이라고 하자.

예를 들어 N = 5 이고, 민균이가 N번동안 빌린 돈이 A = {1, 5, 4, 3, 8} 인 경우, 

• S(1) = 0 (어떻게 선택해도 추가적으로 갚을 돈은 없음)
• S(2) = 1 (2, 3일 분을 갚거나 3, 4일분을 갚는 경우 추가적으로 1을 더 갚으면 됨)
• S(3) = 3 (2, 3, 4 일분을 갚는 경우 추가적으로 3을 더 갚으면 됨)
• S(4) = 7 (1, 2, 3, 4일분을 갚는 경우 추가적으로 7을 더 갚으면 됨)
• S(5) = 19 (1, 2, 3, 4, 5일분을 갚는 경우 추가적으로 19를 더 갚아야 됨)

이제 여러분이 할 일은 민균이가 돈을 빌린 횟수 N 과 N번동안 각각 빌린 돈 A(1), A(2), …, A(N)이 주어졌을 때, S(i) 의 합 S(1), S(2), …, S(N)을 구하는 것이다.

 

입력

---

먼저 테스트케이스의 수 T가 주어지고 이어져서 각각의 줄에 N과 A(i)의 정보가 차례대로 주어진다.

 

출력

---

각각의 줄에 대해 S(1) + … + S(N) 을 구한다. 중간 과정 및 답은 int 범위를 초과할 수 있으므로, 64bit 정수형(long long: C/C++, long: Java) 를 이용해야 한다. 입출력은 

C/C++: printf("%lld\n",answer);
Java : System.out.println(answer);

로 할 수 있다.

 

문제 풀이

---

정렬을 이용한 그리디 문제.

갚아야 할 돈은 선택한 것 중 금액이 큰 것 * M이고, 원래 갚아야 할 돈은 M개 선택한 금액의 합이며, 갚아야 할 돈과 원래 갚아야 할 돈의 차이가 가장 적도록 해야 한다. 따라서 선택할 때 금액이 가장 큰 것과 금액이 가장 작은 것의 차이가 가장 작도록 해야 갚아야 할 돈의 차이가 적다. 즉, 선택한 것 중 금액이 가장 큰 것을 포함하여 내림차순 M개를 선택하면 가장 큰 금액의 빚에 대해 갚아야 할 돈의 차이가 적게 된다.

정렬한 후 누적합을 이용하면 원래 갚아야 할 돈을 구할 수 있다. M이 1일 때부터 N일 때까지 S(M)을 구해 모두 더하면 답이다.

 

예를 들어 입력 예제 1의 테스트 케이스 1에서 S(3)을 구해보자.

5 1 5 4 3 8

오름차순 정렬하면 1 3 4 5 8이다.

S(3)을 구한다고 하면, 가장 큰 것은 4부터 선택할 수 있다. 가장 큰 것이 4라면 1 3 4를 선택해야 금액의 합이 가장 크다. 원래 갚아야 할 빚은 8이고, 민균이가 갚아야 할 빚은 4*3=12이다. 이 둘의 차이는 4이다.

그 다음은 5를 선택한다고 해보자. 가장 큰 것이 5라면 3 4 5 를 선택해야 금액의 합이 가장 크다. 원래 갚아야 할 빚은 12이고, 민균이가 갚아야 할 빚은 5*3=15이다. 이 둘의 차이는 3이다.

가장 큰 빚이 8이라고 한다면 4 5 8을 선택해야 금액의 합이 가장 크다. 원래 갚아야 할 빚은 20이고, 민균이가 갚아야 할 빚은 8*3=24이다. 이 둘의 차이는 4이다.

따라서 S(3)은 이 중 가장 작은 3이 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#define MAX 987654321
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int T, N;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		cin >> N;
		int* arr = new int[N];
		long long* sum = new long long[N + 1];
		long long answer = 0;
		sum[0] = 0;
		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
		}
		sort(arr, arr + N);
		for (int i = 1; i < N + 1; i++)
		{
			sum[i] = sum[i - 1] + arr[i - 1];
		}
		for (int M = 1; M <= N; M++)
		{
			long long currentDayMin = MAX;
			for (int i = M; i <= N; i++)
			{
				long long currentDebt = arr[i - 1] * M;
				long long originalDebt = sum[i] - sum[i - M];
				long long additionalDebt = currentDebt - originalDebt;
				if (additionalDebt < currentDayMin)
				{
					currentDayMin = additionalDebt;
				}
			}
			answer += currentDayMin;
		}
		cout << answer << "\n";
	}
	return 0;
}