[알고리즘] 큰 수의 법칙 (그리디 알고리즘)

큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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 + 4 => 28

 

 

 

---

입력 조건

• 첫째 줄어 N(2 <= N <= 1000), 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

 

 

---

 

 

풀이

맨 처음에는 각 인덱스의 수를 K번만 더할 수 있다고 생각해서 풀었는데, 알고보니 아니었다..!

문제 조건을 다시 읽어보니, K번을 초과하여 중복으로 더할 수 없는 것이지, K번 더한 후 다른 수를 한번 더한 후 다시 더할 수 있었던 것이다.

따라서 입력받은 배열에서 가장 큰 수와 두번째로 큰 수만 있으면 문제를 해결할 수 있다.

 

추가하여

필자의 처음 짠 코드를 올리기 보다는, 이후 책에 나와있는 아이디어를 사용한 코드를 올리겠다.

아이디어는 이러하다.

while을 사용하여 수를 계속 더해가는 방법은 M이 10000 이상의 큰 수를 입력받으면 시간초과가 발생할 가능성이 높다.

이 문제를 해결하기 위해 다음과 같은 아이디어를 제시한다.

우선 N이 5이고 다음과 같은 배열이 주어졌다고 가정한다.

2

4

5

4

6

이때 가장 큰 수와 두 번째로 큰 수는 6과 5이다.

이때 M이 8이고, K가 3이라면 다음과 같이 더했을 때 합이 최대이다.

{ 6, 6, 6, 5 }  { 6, 6, 6, 5 }

 

이 문제를 풀려면 가장 먼저 반복되는 순열에 대해서 파악해야 한다.

가장 큰 수와 두번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.

 

이때 반복되는 수열의 길이는 어떻게 될까?

바로 (K + 1)로 위의 예시에서는 4가 된다.

따라서 M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수가 되며, 여기에 K를 곱해주면 가장 큰 수가 더해지는 횟수가 된다.

 

그런데 M이 (K + 1)로 나누어 떨어지지 않는 경우도 있다. 그럴 때는 M을 (K + 1)로 나눈 나머지를 추가로 더해주면 가장 큰 수가 등장하는 횟수가 된다.

 

가장 큰 수가 더해지는 횟수 : [{M / (K + 1)} * K] + {M % (K + 1)}
두번째로 큰 수가 더해지는 횟수 : M - 가장 큰 수가 더해지는 횟수

 

 

---

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class 큰_수의_법칙 {
    /**
     * 배열의 크기 :N ( 2<= N <= 1000)    ->   O(N^2) 정도까지 가능할 것 같은 (1초 기준)
     * 숫자가 더해지는 횟수 :M ( 1 <= M <= 10,000)
     * 배열의 특정한 인덱스에 해당하는 숫자가 연속으로 더해질 수 있는 최대 횟수 : K (1 <= K <= 10,000)
     *
     *  K는 항상 M보다 작다
     */

    private static ArrayList<Integer> arr =new ArrayList<>();

    private static int arrSize;//N

    private static int addCount;//M

    private static int maxDuplicateCount;//K

    private static int result = 0;

    private static int largestCount;
    private static int secondLargestCount;


    public static void main(String[] args) {

        setInput();

        sortArray(Comparator.reverseOrder());//내림차순 정렬
        
        setLargestCounts();

        calculateMaxNumber();

        System.out.println(result);
    }

   
    private static void setInput(){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        try (br) {
            String[] inputs = br.readLine().split(" ");
            arrSize = Integer.parseInt(inputs[0]);
            addCount = Integer.parseInt(inputs[1]);
            maxDuplicateCount = Integer.parseInt(inputs[2]);



            arr = new ArrayList(Arrays.stream(br.readLine().split(" "))
            			.map(Integer::parseInt).toList());

        } catch (IOException e) {
            e.printStackTrace();
        }

    }

    private static void sortArray(Comparator comparator) {
        arr.sort(comparator);
    }
    
     private static void setLargestCounts() {
        largestCount = arr.get(0);
        secondLargestCount = arr.get(1);
    }


    private static void calculateMaxNumber() {

        int duplicateCount = (addCount / (maxDuplicateCount + 1)) * maxDuplicateCount;//N을 K+1 로 나눈다 -> (가장 큰 수 K번 + 그다음수 1번)이 반복되므로,
        duplicateCount +=  addCount % (maxDuplicateCount + 1);  //나누어지지 않을 경우 나머지가 추가로 더해주어야 할 개수

        result += largestCount * duplicateCount;
        result += secondLargestCount * (addCount - duplicateCount);
    }


}

 

 

 

 

 

 

📔 Reference

[이것이 취업을 위한 코딩 테스트다 - 나동빈]

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체