BOJ_19590_비드맨 (Java)

[Gold I] 비드맨 - 19590

문제 링크

성능 요약

메모리: 28228 KB, 시간: 268 ms

분류

그리디 알고리즘

제출 일자

2024년 11월 3일 16:10:57

문제 설명

구슬을 엄청 좋아하는 비드맨이 있다. 구슬만 보면 갖고 싶어 하는 비드맨은 오늘도 갖고 싶은 구슬을 발견했다. 그러나 비드맨은 현재 구슬을 너무 많이 갖고 있기 때문에 더 이상 구슬을 가질 수 없는 지경에 이르렀다.

비드맨은 서로 다른 종류의 구슬 두 개를 부딪히면 서로 깨져 없어진다는 것을 알고 있다. 이 사실을 이용해서 비드맨은 현재 가지고 있는 구슬의 개수를 최소로 하고자 한다. 그러나 구슬의 개수가 많기 때문에 비드맨은 도저히 계산을 할 수가 없었다.

길거리 해결사인 당신은 길거리에서 고민에 빠진 비드맨을 발견했고, 비드맨에게 고민에 빠진 이유를 듣게 된다. 인연인 만큼 당신은 비드맨의 고민을 해결해주려고 한다. 서로 다른 종류의 구슬 두 개를 부딪혀서 최대한 구슬을 없앤다고 할 때 남게 되는 구슬의 개수는 몇 개인지를 구하면 된다.

입력

첫 번째 줄에는 비드맨이 가지고 있는 구슬의 종류 N이 주어진다. (1 ≤ N ≤ 10⁵)

두 번째 줄부터 N개의 줄에는 x₁, x₂​, x_3, ..., x_N이 주어진다. x_i는 비드맨이 가지고 있는 i번째 종류의 구슬의 개수이다. (1 ≤ x_i ≤ 10⁹)

출력

비드맨이 최대한 많이 구슬을 없앴을 때 남는 구슬의 개수를 출력한다.

문제 풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;
public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N;
	static long[] bead;
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}
	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		bead = new long[N];
		
		for(int i=0; i<N; i++) {
			long beadNum = Long.parseLong(br.readLine());
			bead[i] = beadNum;
		}
		
		PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder()); // 최대힙
		
		for(long n : bead) 
			pq.offer(n);
		
		if(N==1) {
			bw.write(String.valueOf(bead[0]));
		}
		else {
			long max = pq.poll();
			
			long sum = pq.stream()
					.mapToLong(Long::longValue)
					.sum();
			
			long totalSum = sum + max;
			
			if(max > sum) {
				bw.write(String.valueOf(max - sum));
			}
			else {
				if(totalSum %2 == 0) bw.write(String.valueOf(0));
				else bw.write(String.valueOf(1));
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}