[이것이 코딩 테스트다] (Ch03 그리디) 큰 수의 법칙

 

 

---

언어_자바

이것이 코딩 테스트다_92p~95p 큰 수의 법칙

 

---

 

 

N: 배열의 크기
M: 숫자가 더해지는 횟수
K: 최대 가능한 연속성 횟수 

입력 예시
5 8 3
2 4 5 4 6

public class _92BigNum {

    static Integer n;
    static Integer m;
    static Integer k;
    static Integer first, second;
    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());

        st = new StringTokenizer(br.readLine());
        int[] number = new int[n];

        for(int i =0; i < n; i++){
            number[i] = Integer.parseInt(st.nextToken()); // 2 4 5 4 6 을 입력한다
        }
        Arrays.sort(number); // 2 4 4 5 6

        first = number[n-1]; // 가장 큰 수(= 배열의 마지막 요소 )
        second = number[n-2]; // 두 번째로 큰 수(= 배열의 마지막에서 앞 요소)
        simpleSolution();
        advancedSolution();

    }

    static void simpleSolution(){
        System.out.println("[93p 단순하게 푸는 솔루션]");

        int localM = m.intValue();
        int result = 0;

        while (true){
            for(int i = 0; i <k; i++){
                if(localM == 0) break; // m이 0이라면 반복문 탈출
                result += first;
                localM -= 1; // 더할 때마다 횟수 1씩 빼기
            }
            if(localM == 0) break;
            result += second; // 두 번째로 큰 수는 한 번 더하기 (반복문 밖)
            localM -= 1; // 더할 때마다 횟수 1씩 빼기
        }
        System.out.println("result : "+ result);
    }

    static void advancedSolution(){
        System.out.println("[95p 최적화 솔루션]");

        int count = (m / (k+1)) * k + m % (k+1); // 가장 큰 수가 더해지는 횟수 및 나머지가 생길 경우
        int remain = m -count;  // 나머지 횟수

        int result = count * first + remain * second;
        System.out.println("result : "+ result);
    }

}

최적화 솔루션에 대한 설명을 하자면, 반복되는 수열을 활용한 풀이법이다.
위의 예시에서는 {6,6,6,5} 가 반복이 총 2회 되는 것을 알 수 있다. =>  {6,6,6,5} {6,6,6,5}
그렇다면 반복되는 수열의 길이는 4인 M을 (K+1)로 나눈 몫이 반복되는 횟수임을 알 수 있다. 
여기서 중요한 점은 M이 (K+1)로 나누어 떨어지지 않는 경우도 고려해야한다. 

즉, 가장 큰 수가 더해지는 횟수는 다음과 같은 공식이다.
int (M / ( K + 1 )) * K + M % (K+1) 

(M/(K+1)) * K => 반복되는 횟수 * 최대 가능한 연속성 횟수 
 M % (K+1) => 나머지 

라 볼 수 있다. 
따라서 , count 는 가장 큰 수가 더해지는 수이므로 6이 나온다. 
remain의 값은 2가 나온다. {6,6,6,5} {6,6,6,5}에서 가장 큰 수를 제외한 두 번째로 큰 수인 5의 총 횟수이다. 

int result 의 식은 결국 풀어적자면, 6 * 6 + 2 * 5 = 46라고 할 수 있다. 

 

 

 

 

 

 

<Reference>

https://www.yes24.com/Product/Goods/91433923