[이.코.테] Chapter 03 그리디 - 큰 수의 법칙 (Java)

그리디 알고리즘

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

큰 수의 법칙 문제 (교재 92p)

난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 2019 국가 교육기관 코딩 테스트

 

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

배열의 크기 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
5 7 2 3 4 3 4 3	28

 

---

문제 풀이 방법 1

• 입력값 중에서 가장 큰 수와 작은 수만 저장하면 됨
• 가장 큰 수 K번 더하고, 두번째로 큰 수를 한 번 더하는 걸로 반복

 

소스코드

package exam03_greedy;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q2_HighNumber{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 배열의 크기
        int m = Integer.parseInt(st.nextToken()); // 숫자가 더해지는 횟수
        int k = Integer.parseInt(st.nextToken()); // 연속해서 더할 횟수

        int[] 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); // 배열 오름차순 정렬
        int first = arr[arr.length-1]; // 가장 큰 수
        int second = arr[arr.length-2]; // 두번째로 큰 수
        int result = 0;

        // while문으로 m번 만큼 반복
        while (m != 0) {
            // 가장 큰 수 k번 더함
            for (int j = 0; j < k; j++) {
                result += first;
                m--; // 횟수 차감
            }
            // 두번째로 큰 수 한 번 더함
            result += second;
            m--; // 횟수 차감
        }

        bw.write(result+"\n");

        br.close();
        bw.close();

    }
}

 

---

문제 풀이 방법 2

* 배열의 크기 N, 숫자가 더해지는 횟수 M, 초과 제한 횟수 K

 

• 반복되는 수열 파악
  - {가장 큰 수 K번 + 두번째 큰 수}
• 수열의 길이 = K + 1
• 따라서 M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수
  나누어 떨어지지 않을 때는 M을 (K + 1)로 나눈 나머지 만큼 가장 큰 수가 추가로 더해짐

👉 결론!
     가장 큰 수가 더해지는 횟수 : ( M / (K + 1) ) * K  +  M % ( K + 1 )
     두번째 수가 더해지는 횟수 : M - {가장 큰 수가 더해지는 횟수}

 

package exam03_greedy;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q2_HighNumber2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 배열의 크기
        int m = Integer.parseInt(st.nextToken()); // 숫자가 더해지는 횟수
        int k = Integer.parseInt(st.nextToken()); // 연속해서 더할 횟수

        int[] 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); // 배열 오름차순 정렬
        int first = arr[arr.length-1]; // 가장 큰 수
        int second = arr[arr.length-2]; // 두번째로 큰 수

        int numFirst = (m / (k + 1)) * k + m % (k + 1); // 가장 큰 수가 더해지는 횟수
        int numSecond = m - numFirst; // 두번째로 큰 수가 더해지는 횟수

        int result = numFirst*first+numSecond*numSecond;


        bw.write(result+"\n");

        br.close();
        bw.close();

    }
}