[Java] 백준 19539번 사과나무

그리디 문제입니다.

물뿌리개 2개가 주어집니다.
1. 1의 높이를 올리는 물뿌리개
2. 2의 높이를 올리는 물뿌리개

2개의 물뿌리개를 이용해서 나무의 높이를 주어진 높이로 정확히 맞출 수 있는지 구해야 합니다.

먼저 3으로 나누어 떨어지는지 확인했습니다.
3으로 나누어 떨어지지 않는 경우는 불가능한 경우입니다.

한번에 1과 2를 사용하며, 2의 경우 1을 2개 사용해서 만들 수 있습니다.
1의 경우 2를 이용해서 만들 수 없습니다.
중요한건 1의 개수가 2의 개수보다 많은지 찾으면 됩니다.

최대한 2를 많이 쓰는 방향으로 생각해봅니다.
11 => 2 2 2 2 2 1
10 => 2 2 2 2 2
7 => 2 2 2 1
3 => 2 1
1 => 1

위를 보았을 때 규칙은 1의 개수는 2로 나누어 떨어지지 않는 수는 1을 하나 가집니다.
모든 수에 위처럼 2와 1의 개수를 나누어서 카운트해줍니다.

1이 2보다 많은 경우 실패한 경우로 출력해주었습니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());
    int sum = 0;
    int one = 0;
    int two = 0;
    String result = "YES";

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      int num = Integer.parseInt(st.nextToken());
      sum += num;
      one += num % 2;
      two += num / 2;
    }

    if (sum % 3 > 0 || one > two) {
      result = "NO";
    }

    bw.write(result + "\n");
    bw.close();
  }
}