🥇[백준, 2878] 캔디캔디 (Java)

 

문제 링크

https://www.acmicpc.net/problem/2878

2878번: 캔디캔디

 

난이도

 

시간제한

1초

 

문제

오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다.
택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질수록 더욱 분노하게 된다.
놀랍게도 택희는 친구들의 분노를 수치화할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다.
예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다.
택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어 하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 최소화해 그 값을 출력하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

입출력 예시 1

입력

5 3
1
3
2

 

출력

1

 

입출력 예시 2

입력

10 4
4
5
2
3

 

출력

4

---

문제 풀이 과정

예시를 통해 문제 이해하기

 

입출력 예시 2를 살펴보자.

총 10개의 사탕이 존재하고 이것을 4명의 친구에게 나누어줘야 한다.

 

여기서 친구에게 몇 개씩 나눠주면 분노가 최소가 될지를 생각하기는 매우 어렵다.

그 대신 못 받을 사탕을 분배한다고 생각해 보자.

 

총 10개의 사탕이 존재하고 4명의 친구가 받고 싶어 하는 사탕의 개수는 다음과 같다.

4 5 2 3

즉, 친구들의 분노를 사지 않으려면 총 14개의 사탕이 필요하다.

하지만 위에서 말했듯 나눠줄 수 있는 사탕은 10개뿐이다..🥲

 

따라서 결국 친구들은 총 4개의 사탕을 받지 못하게 되고 그것은 분노가 된다.

❓4명의 친구들에게 받지 못할 4개의 사탕을 어떻게 분배해야 분노의 합이 최소가 될까?

 

4명에게 1개씩 분배하면 분노의 합이 총 4로 최소가 된다.

받지 못할 사탕을 최대한 균등하게 친구들에게 배분하면, 그것이 분노의 합을 최소화하는 방법이다!

 

입력값 저장하기

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[] friends = new int[N];


for (int i = 0; i < N; i++) {
    friends[i] = Integer.parseInt(br.readLine());
}

친구들의 수만큼 반복문을 돌며 friends배열에 각 친구가 받고 싶어 하는 사탕의 개수를 저장한다.

 

받지 못할 사탕을 균등하게 나눠주는 코드 구현하기

 

새로운 예시를 들어 살펴보자.

1 5 4 3

친구들이 받고 싶어 하는 사탕의 총합은 13이고 친구는 4명이다.

총 11개의 사탕을 친구들은 받지 못하게 된다고 가정하자.

 

위에서 말했듯 이를 4명의 친구에게 균등하게 나누면 11 / 4 = 2.75이므로 우선 각각 2개씩 분배해 보자.

 

여기서 문제가 발생한다.

❓1개의 사탕을 받고 싶어 하는 친구에게 2개의 사탕을 받지 못하게 분배할 수 있을까?

불가능하다.

 

따라서 배열의 정렬이 필요하다.

1 3 4 5

 

1단계

첫 번째 친구에게는 분배한 받지 못할 사탕의 수(2), 받고 싶어하는 사탕의 수(1)중 더 작은 값이 1이므로 1개를 받지 못하도록 한다.

그 이유는 본인이 원하는 사탕의 수보다 더 많이 받지 못할 수는 없기 때문이다.

 

2단계

나머지 사탕은 11개에서 1개를 뺀 10개가 된다.

이제 총 3명에게 10개의 사탕을 균등하게 분배해야 한다.

3 4 5

균등하게 나누면 10 / 3 = 3.3.. 이므로 각각 3개씩 분배한다.

두 번째 친구는 분배한 사탕의 수와 받고 싶어 하는 사탕의 수가 같기 때문에 3개를 분배한다.

 

3단계

나머지 사탕은 10개에서 3개를 뺀 7개이다.

이제 총 2명에게 7개의 사탕을 균등하게 분배해야 한다.

4 5

균등하게 나누면 7 / 2 = 3.5이므로 각각 3개씩 분배한다.

세 번째 친구는 분배한 사탕의 수보다 받고 싶어하는 사탕의 수가 크기 때문에 3개를 분배한다.

 

4단계

나머지 사탕은 7개에서 3개를 뺀 4개이다.

총 1명에게 4개의 사탕을 분배하면 되므로 마지막 친구에게 4개를 분배한다.

 

이를 코드로 구현하면 다음과 같다.

Arrays.sort(friends);

long count = sum - M;
long anger = 0;

// 최대한 균등하게 분배
for (long friend : friends) {
    long candy = Math.min(friend, count / N--);
    anger += candy * candy;
    count -= candy;
}

System.out.println(anger % (long) Math.pow(2, 64));

 

Math.pow를 사용하게 되면 double형을 return 하므로 앞에 (long)으로 타입을 지정하여 최종 분노의 합을 출력한다.

 

주의해야 할 점!!

분명 맞게 한 것 같은데 틀렸다고 나온다면 자료형을 의심해 보자.

 

M의 범위는 1 이상 2 * 10^9 이하인 값이다.

int 자료형의 범위는 -2^31 ~ 2^31-1, 즉 2^10을 10^3으로 치환하면 대략 ~ 2 ^ 10^9의 범위가 된다.

 

따라서 N만 int형이 가능하고 나머지의 값들은 long형을 사용해야 한다.

 

최종 코드

 

public class BOJ_2878 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        long[] friends = new long[N];
        long sum = 0;

        for (int i = 0; i < N; i++) {
            friends[i] = Integer.parseInt(br.readLine());
            sum += friends[i];
        }

        Arrays.sort(friends);

        long count = sum - M;
        long anger = 0;

        // 최대한 균등하게 분배
        for (long friend : friends) {
            long candy = Math.min(friend, count / N--);
            anger += candy * candy;
            count -= candy;
        }

        System.out.println(anger % (long) Math.pow(2, 64));
    }
}