[Algorithm] 큰 수의 법칙

#그리디 #알고리즘 #코딩테스트 #자바 #이것이_코딩테스트다

 

문제

다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

입력조건

첫째 줄에 N, M, K의 자연수가 주어지며, 공백으로 구분한다.

둘째 줄에 N개의 자연수가 주어진다.

 

풀이

먼저, 가장 큰 수가 K번 초과할 수 없을 때, 그 다음 큰 수를 활용해야하기 때문에, N개의 자연수를 정렬했다.

정렬하고 나서 가장 큰 수와 그 다음 큰 수를 활용했다.

가장 큰 수가 K번, 그 다음 큰 수가 1번이 하나의 싸이클로 생각했다.

M에서 K+1의 크기를 가진 싸이클이 몇 번 나오는지 M / (K+1)로 계산했고,

나머지 M % (K+1) 만큼 가장 큰 수로 채우면 된다고 생각했다.

 

import java.util.*;

class Main {
  
  public static void main(String[] args) {
    // 배열의 크기 n, 숫자 더 해지는 횟수 m
    // 하나의 인덱스 최대 k번
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int k = sc.nextInt();
    
    int[] input = new int[n];
    for (int i = 0; i < n; i++) {
      input[i] = sc.nextInt();
    }
    sc.close();

    //먼저, 받은 숫자를 정렬 (가장 큰 수와 그 다음 큰 수)
    Arrays.sort(input);
    int first = input[n-1];
    int second = input[n-2];

    // first * k + second 가 m / k+1 만큼 들어가고,
    // first가 m % k+1 만큼 더 들어가면 된다.

    int result;
    result = ((m / (k + 1)) * (first * k + second))
                + (m % (k+1)) * first;
    
    System.out.print(result);

  }

}