[Algorithm] 그리디 알고리즘 문제 풀이 - 큰 수의 법칙

그리디 알고리즘 문제 풀이 - 큰수의법칙

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 그리디 알고리즘 문제 중 '큰수의 법칙' 문제와 풀이를 설명합니다.

문제

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

 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 예를 들어 순선대로 2, 4, 5, 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 + 4 + 4인 28이 도출된다.

 

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오. 

 

🎁입력 조건

1. 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.

3. 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

🎊출력 조건

첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

🎁입력 예시

5 8 3

2 4 5 4 6

 

🎊출력 예시

46

 

문제 해설1

문제를 해결하려면 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. 연속으로 더할 수 있는 횟수는 최대 K번으므로 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다.

 

내가 작성한 자바 코드

import java.util.*;

public class 큰수의법칙 {
    public static void main(String[] args){
        int N, M, K;
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();

        Integer arr[] = new Integer[N];

        for(int i =0; i < N ; i++){
            arr[i] = scanner.nextInt();
        }
        scanner.close();
        
		// 입력 받은 숫자를 오름차순으로 정렬
        Arrays.sort(arr, Collections.reverseOrder());

        int result = 0;	// 결과의 합을 저장할 변수
        int count = 0;	// 연속으로 몇 번 숫자가 더해졌는지 기록하는 변수

        for(int i =0; i < M ; i++){
            if(count<K){	
           		//입력 받은 가장 큰 수를 연속으로 K번 미만으로 더한다. 
                result += arr[0];
                count++;
            }else{	
            	//입력 받은 가장 큰 수를 연속으로 K번 이상 더했다면 두 번째로 큰 수를 한 번 더하고
                //count를 다시 0으로 초기화한다.
                result += arr[1];
                count = 0;
            }
        }

        System.out.println(result);
    }
}

 

문제 해설2

 

이 문제는 M이 10,000 이하이므로 이 방식으로도 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받는다. 간단한 수학적 아이디어로 더 효율적으로 문제 해결이 가능하다.

 

예를 들어 N이 5이고, 입력값은 2 4 5 4 6 이다. 이때 가장 큰 수는 6 두 번째로 큰 수는 6이다. 이때 M이 8이고, K가 3이라면 (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5)로 정답은 46이 된다. 이 문제는 반복되는 수열이 존재한다. 가장 큰 수와 두 번째로 큰 수 가 더해질 때 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다. 

 

위의 예시에서는 (6,6,6,5)가 반복되고, 반복되는 수열의 길이는 K+1이다. 따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.  여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다. 이때 M이 (K+1)로 나누어 떨어지지 않는 경우도 있다. 이런 경우 M을 (K +1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해진다. 

 

따라서 가장 큰 수가 더해지는 횟수(count)는 다음과 같다.

 

count = int(M/K+1)*K + M % (K + 1)

 

그리고 두 번째로 큰 수가 더해지는 횟수는 다음과 같다.

 

M - count

 

내가 작성한 자바 코드

import java.util.*;

public class 큰수의법칙 {
    public static void main(String[] args){
        int N, M, K;
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();

        Integer arr[] = new Integer[N];

        for(int i =0; i < N ; i++){
            arr[i] = scanner.nextInt();
        }
        scanner.close();

        Arrays.sort(arr, Collections.reverseOrder());

        int first = arr[0];  //가장 큰 수
        int second = arr[1]; //두 번째로 큰 수
        int sum1 = 0; //가장 큰 수의 합
        int sum2 = 0; //두 번째로 큰 수의 합

        // 수열의 길이 K+1
        // 수열 반복 횟수 M/(K+1)
        // 가장 큰 수가 나오는 횟수 count = K * M/(K+1) + M%(K+1)
        // 두 번째 큰 수가 나오는 횟수 M - count
        int count =  (K * M/(K+1) + M%(K+1));
        sum1 = first * (K * M/(K+1) + M%(K+1));
        sum2 = second * (M - count);

        System.out.println(sum1 + sum2);
    }
}

 

저자 풀이

github.com/ndb796/python-for-coding-test/blob/master/3/2.java