동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
예를 들어, 순서대로 2, 4, 5, 4, 6 으로 된 배열이 있을 때, M이 8이고, K가 3이라고 가정했을 때, 큰 수의 법칙으로 6+6+6+5+6+6+6+5인 46이 되게 된다.
단, 서로 다른 인덱스에 해당하는 수가 동일한 수라도 서로 다른 것으로 간주한다. 예를 들어, 3, 4, 3, 4, 3이 있을 때, M이 7이고, K가 2라고 가정하자. 그렇다면 큰 수의 법칙 결과, 4+4+4+4+4+4+4인 28이 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/* 큰 수의 법칙 */
public class greedy_02 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st1.nextToken());
int M = Integer.parseInt(st1.nextToken());
int K = Integer.parseInt(st1.nextToken());
// 배열 생성 및 초기화
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(arr); // 배열 정렬
int first = arr[N-1]; // 첫번째로 큰 수
int second = arr[N-2]; // 두번째로 큰 수
int answer = 0; // 결과
while (M != 0) {
// 가장 큰 수를 최대한 많이 더함
for (int i = 0; i < K; i++) {
answer += first;
M--;
}
// 그 다음 큰 수를 한번 더함
answer += second;
M--;
}
System.out.println(answer);
}
}
Arrays.sort
메소드를 통해 정렬 후 그대로 사용M
이 0이 될 때까지 반복