제한 조건
- 풀이시간 : 30분
- 시간 제한 : 1초
문제
'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.
예를 들어, 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고, K가 3이라고 하자. 이 경우 특정한 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6+ 6 + 5 = 46이 된다.
마찬가지로 Array = {3, 4, 3, 4, 3}, M = 7, K = 2일 때, 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28이 된다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때, 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.
입력 조건
- 첫째 줄에
N(2 <= N <= 1,000),M(1 <= M <= 10,000),K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. - 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의
자연수는 1 이상 10,000 이하의 수로 주어진다. - 입력으로 주어지는
K는 항상 M보다 작거나 같다.
출력 조건
- 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.
예시
| 입력 | 출력 |
|---|---|
| 5 8 3 2 4 5 4 6 | 46 |
풀이
이 문제의 포인트는 가장 큰 수를 K번 더한 후 그 다음 큰 수를 더하면, 다시 가장 큰 수를 K번 더할 수 있다는 것이다. 이 패턴을 활용하여 M번만큼 더한 결과를 가져오면 된다.
먼저 가장 큰 수와 두번째로 큰 수를 구하기 위해서는 주어진 배열을 정렬해야 한다.
Collections.sort를 활용하면 O(nlog(n))의 시간 복잡도로 정렬할 수 있다.
정렬된 배열에서 last index와 last index - 1이 가장 큰 수와 두번째로 큰 수가 된다.
이 후 M번만큼 덧셈을 수행하며, last index를 더하다가 counter를 활용해 K번을 넘으면 last index - 1 더해주는 과정을 반복한다.
결과적으로 O(nlog(n) + m), n = 배열의 크기, m = 숫자가 더해지는 횟수의 시간 복잡도로 풀이할 수 있다.
코드
