[백준 10427] 빛 [Java]

문제

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

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

먼저, 김우현 연구소가 민균이에게 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);

로 할 수 있다.

---

풀이

문제에서 주어지는 S에 대해 정의하자.

"김우현 연구소"가 M번의 빚을 갚으라고 하면, A에 대해 M개를 고르고, 그 중 최댓값을 M과 곱한 값에 고른 M개의 합을 뺀 값이다.

S(i) = min(S(i -1), max(A[i, i ~M]) * M - sum( A[i, i ~M] ))

 

이제 문제를 해결해보자.

우선 입력은 배열의 길이와 요소를 한 줄로 준다.

이를 분리해주자.

배열의 길이는 A.length로 바로 알 수 있다. 저장할 필요가 없다.

이제 입력받은 A를 정렬해주고, 누적합을 구해주자.

배열의 정렬과 누적합을 이용해 A[i, i ~M]에 대해 M개의 요소를 고르는 방식이 아닌, 순차적으로 선택하는 방식으로 쉽게 해결할 수 있다.

이제 S(2) ~ S(N)의 합을 구하자.

정렬된 A에 대한 누적합은 슬라이딩 윈도우 기법을 이용해 M 요소의 합을 구할 수 있다.

또한 A는 정렬되어 있기 때문에 max(A[i, i ~M])또한, 순차적으로 지정하면 된다.

S에 대해 다음과 같이 구현할 수 있다.

---

소스코드

보기

---

출처

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