백준 21187 자바 - Pulling Their Weight (BOJ 21187 JAVA)

문제 : https://www.acmicpc.net/problem/21187

 

 

  뭔가 복잡해보이는데, 좀 정리해보면 그냥 brute force로 해결 가능한 문제이다.

 

1

  최대 10^5개의 동물의 무게가 주어진다. 그리고 각 무게는 2만 이하이므로, 전부 더해도 20억 이하로 Integer로 표현 가능한 수치이다.

 

 

2

  사실 동물이 몇마리가 주어지든 상관없고 중요한 데이터는 결국 '1~20,000 사이의 각 무게를 가진 동물이 각 몇마리씩 존재하는지' 이다.

 

 

3

  정렬이 필요할것같이 생겼지만, 사실 무게가 2만 이하라서 배열에 카운팅한다면 정렬은 따로 필요 없다. 다음의 입력을 보자.

6
5
7
5
5
3
4

위 입력을 배열로 카운팅해보면 다음과 같다.

 

 

4

  그럼 이제 index 기준으로 1부터 20000까지를 문제에서 요구하는 'target weight t' 로 가정하며 brute force로 진행해보면 된다.

 

  이 때 't'를 기준으로 t보다 낮은 값과 높은 값은 어떻게 구할 수 있을까? 보통 이럴 때 사용하는 prefix sum으로 해도 되지만, 단순히 미리 모든 값을 더해두고 어차피 index를 1부터 진행할 것이므로 낮은값을 새로 구해나가도 된다. t보다 낮거나 같은 값을 'left', 높은 값을 'right'라고 할 경우, t를 증가시키면서 배열의 값을 토대로 left를 계속 더해갈 경우 right는 '입력된 모든 무게의 합(sum) - left'가 된다.

 

  그렇게 계속 left를 더해나가면서 문제에서 제시된 짝수, 홀수 규칙에 따라 비교를 해서 답이 충족되는 경우 바로 출력하면 'If there are multiple such t, he wants the smallest one.' 조건도 충족하면서 답을 구할 수 있다.(답이 없는 경우는 없다고 했으므로 이에 대한 예외처리는 필요없음)

 

 

예시

A. 전체 무게의 합 sum = 29 (입력 받으면서 미리 구해두면 됨)

 

B. t=1, 2일 경우

-> left = 0

-> right = sum - left = 29

-> 0 != 29 이므로 답이 아니다.

 

C. t = 3일 경우

-> left = left + 3 = 3

-> right = 29 - 3 = 26

-> t = 3과 일치하는 배열의 값은 홀수이다. 따라서 버려진다. 0 != 26 이므로 답이 아니다.

 

D. t = 4일 경우

-> left = left + 4 = 7

-> right = 29 - 7 = 22

-> t = 4인 부분은 홀수이다. 따라서 버려지고, 3 != 22 이므로 답이 아니다.

 

E. t = 5일 경우

-> left = left + 5*3 = 22

-> right = 29 - 22 = 7

-> t = 5인 부분은 홀수이다. 따라서 버려지고, 7 == 7 이므로 답이다. 5를 출력하고 그대로 끝내면된다!

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/21100/BOJ_21187.java

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int[] cnt = new int[20001];
        int sum = 0;
        while (n-->0) {
            int a = nextInt();
            sum += a;
            cnt[a]++;
        }
        int left = 0;
        int right = 0;
        for (int i = 1; i <= 20000; i++) {
            left += i * cnt[i];
            right = sum - left;
            if (cnt[i] == 0 && left == right) {
                System.out.println(i);
                return;
            }
            if ((cnt[i]&1)==1) {
                if (left-i*cnt[i] == right) {
                    System.out.println(i);
                    return;
                }
            } else {
                if (left-(i*cnt[i]/2) == right+(i*cnt[i]/2)) {
                    System.out.println(i);
                    return;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}