문제

위 문제는 아래 링크의 책의 그리디 파트에 대한 문제입니다. 저작권 문제로 인해 문제를 올리지는 않겠습니다.ㅠㅠ
https://www.youtube.com/watch?v=eYtsGlYPilo

풀이

1. 배열 생성

2. 배열 오름차순으로 정렬

3. arr[N-1]을 연속해서 K번 더한다. 이후 arr[N-2]을 1번 더하고 다시 arr[N-1]을 K번 더한다.
   이 과정을 M번동안 반복한다.

코드

import java.util.*;
import java.io.*;

public class Main {

    static int N, M, K;
    static int[] arr;
    static int answer = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        // 1번째 풀이 (처음 내가 푼 방법)
        // 완전탐색(?)의 방법으로 풀었음.
//        int cnt = 0;
//        for (int i = 0; i < M; i++) {
//            if (cnt == K) {
//                answer += arr[N - 2];
//                cnt = 0;
//            } else {
//                answer += arr[N - 1];
//                cnt++;
//            }
//        }


        // 2번째 풀이
        // 가장 큰 수가 더해지는 횟수 & 그 다음으로 큰 수가 더해지는 횟수를 구함.
        // 1번째 풀이 보다 속도가 더 빠름!
        int first = arr[N - 1];
        int second = arr[N - 2];

        int cnt = (M / (K + 1)) * K;
        cnt += M % (K + 1);

        answer += cnt * first;
        answer += (M - cnt) * second;


        System.out.println(answer);
    }
}