그리디 알고리즘을 이용한 문제

그리디 알고리즘이란?

 그리디 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 되는데, 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이아니라 현 시점의 정보를 바탕으로 가장 이익이 되는 원소들을 선택하는 방법이라고 할 수 있다.

 

 복잡한 과정을 거치지 않고, 상황을 종합적으로 판단하는게 아니기 때문에 매우 빠른 알고리즘이라고 할 수 있다. 이러한 그리디 알고리즘은 최적화 문제를 해결하기 위한 방법이다.

 

2878번: 캔디캔디

캔디캔디

문제

 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다.

택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질 수록 더욱 분노하게 된다.

놀랍게도 택희는 친구들의 분노를 수치화 할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다.

예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다.

택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 최소화해 그 값을 출력하는 프로그램을 작성하시오.

입력

 첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 사탕의 개수의 합은 항상 M을 넘는다.

출력

 첫째 줄에 택희 친구들의 분노의 합의 최솟값을 2^64로 나눈 나머지를 출력한다.

풀이법

 그리디 알고리즘 문제들은 대부분 무엇을 기준으로 정렬할 것인가만 파악하면 해결된다. 이 문제의 핵심은 친구들에게 사탕을 잘 나눠줘야한다. 이는 많이 원하는 친구에게는 조금 더 많이 조금만 원하면 아예 안줘도 된다. 그래서 못 주게 되는 사탕의 수를 저장하는 변수를 남은 사람의 수로 나누면 된다.

 

import java.util.*;

public class Main {
    public static long min(long a, long b) { //최소값 구하는 함수
        return a < b ? a : b;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);//input을 위한 설정
        int M, N;
        M = sc.nextInt();//M개의 사탕 입력
        N = sc.nextInt();//N명의 사람 입력
        int[] candy = new int[N];//N명의 사람이 원하는 사탕 수
        long sum = -1 * (long) M;//sum은 부족한 사탕의 수

        for (int i = 0; i < N; i++) {
            candy[i] = sc.nextInt();//사탕 입력
            sum += (long) candy[i];//sum은 부족한 사탕의 수
        }
        Arrays.sort(candy);//정렬(오름차순)
        long ans = 0;
        for (int i = 0; i < N; i++) {
            long w = Math.min((long) candy[i], sum / (N - i));//원하는 사탕의 수랑 sum/N-i 비교후 작은 값을 w에 저장
            ans += w * w;//분노는 못 받은 사탕 수의 제곱
            sum -= w;//사탕을 give한 만큼 줄여줌
        }
        System.out.println(ans);//출력

    }
}

 

 문제 자체는 크게 어렵지는 않았는데 출력 조건의 '첫째 줄에 택희 친구들의 분노의 합의 최솟값을 2^64로 나눈 나머지를 출력한다.'를 이해하지 못해서 계속 틀렸었다. 2^64로 나눈 나머지라는 뜻이 ~(1 << 64)와 & 연산을 하는것과 동일하므로 long 타입을 쓰면 된다는 것을 나중에 깨닫고(정확히는 어떤 분이 친절하게 정리하신 글을 봄) 해결했다.