18002 : Balanced Animals - JAVA

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

 

주어진 동물을 두 그룹으로 나누고 한 그룹의 무게와 다른 그룹의 무게가 같도록 해야하는 이분 탐색 + 누적 합 문제라고 한다.

다만 나는 이분 탐색을 이용하지 않고 누적 합을 이용하여 순차적으로 두 그룹의 합을 구하였다.

어떠한 그룹에도 속하지 않는 동물을 솎아내는 작업이 필요하다.

입력받은 모든 동물의 무게를 누적합을 이용하여 구했다. 왜냐하면 각 무게를 받은 값에 해당 무게를 갖다주고 순차 누적합 탐색을 하는 것이 이분탐색보다 익숙했기 때문이다. 그리고 같은 무게가 등장하지 않는다는 점도 이렇게 해결할 수도 있다고 생각하게 된 주요 요인이다.

		for(int i = 1; i <= n; i++) {
			int a = sc.nextInt();
			arr[a] += a;
		}
		for(int i = 1; i <max; i++) {
			arr[i] += arr[i-1];
		}

입력 횟수만큼 해당 무게 배열 번호에 해당 값을 더한다.

그리고 배열의 길이만큼 값을 더한다.

무게가 4 7 3 6이었다면

0 0 0 3 7 7 13 20 20 20 20 ...으로 이어진다.

		for(int i = 1; i < max; i++) {
			int l = arr[i];
			int r = arr[max-1] - arr[i-1];
			if(l == r) {
				System.out.println(i);
				break;
			}
		}

아까 배열의 번호에 무게를 넣은것과 그것을 최대길이만큼 더해서 max번에는 결국 모든 무게의 합을 더한 값이 집어넣어져 있다.

JAVA의 int형태 배열의 기본값이 0인것을 이용하여 누적합을 이용하였고 l은 배열의 처음부터 값을 훑고

r은 모든 무게를 더한 값 - 배열의 현재값에서 1을 뺀 값을 이용했다.

그래야 i에서 max만큼 더한 것이 나오기 때문이다.

서로 탐색하여 값이 같아질때 답이 도출되도록 설정했다.

 

소스코드

import java.util.*;

public class Main {
	static int max = 200000;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[(int) max];
		for(int i = 1; i <= n; i++) {
			int a = sc.nextInt();
			arr[a] += a;
		}
		for(int i = 1; i <max; i++) {
			arr[i] += arr[i-1];
		}
		for(int i = 1; i < max; i++) {
			int l = arr[i];
			int r = arr[max-1] - arr[i-1];
			if(l == r) {
				System.out.println(i);
				break;
			}
		}
	}
}