[백준] 19590번 비드맨 Java

문제 링크

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

알고리즘: 그리디

문제

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

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

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

풀이

구슬 종류 중 가장 큰 값을 찾고, 그 큰 값을 제외한 나머지 값은 더해준다.
(max, sum)
1.max > sum 이면
max - sum 값을 출력하고

2.max <= sum 이면
max + sum이 홀수인지 짝수인지 판별한다.
홀수이면 무조건 1이 남고
짝수이면 무조건 0이 된다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static long max_bead = -1;
    static long sum_bead = 0;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      for(int i=0; i<N; i++) {
          long cur_bead = Integer.parseInt(br.readLine());
          sum_bead += cur_bead;
          if(max_bead < cur_bead) {
              max_bead = cur_bead;
          }
      }
      sum_bead -= max_bead;
      if(max_bead > sum_bead) {
          System.out.println(max_bead - sum_bead);
      } else {
          if((max_bead + sum_bead) % 2 == 0) {
              System.out.println(0);
          } else {
              System.out.println(1);
          }
      }
    }
}