[이코테] 그리디 - 큰 수의 법칙 - JAVA

최영환·2022년 10월 7일
0

이코테

목록 보기
2/24
post-thumbnail

💡 문제

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 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이 될 때까지 반복
    1. 첫번째로 큰 수를 최대한 많이(K번) 더함
    2. 두번째로 큰 수를 한 번 더함
profile
조금 느릴게요~

0개의 댓글