[백준/19539] 사과나무 - JAVA

📌 문제

알고리즘 분류 : 그리디 알고리즘
난이도 : 골드5
출처 : 백준 - 사과나무

🦧 문제 풀이 접근

그리디 알고리즘으로 문제를 해결한다.
YES가 되는 두가지 조건이 있다.
1. 기본적으로 모든 숫자의 합이 3의 배수여야 한다.
2. 각각의 숫자를 1과 2로 나타냈을때 1보다 2가 많아야 한다.

2번에 대해 설명하자면 5에 경우 2+2+1이므로 2 -> 2개 1 -> 1개이다.
모든 숫자에서의 1과 2의 갯수를 측정한다.

1,2둘다 성립할경우 YES, 아닐경우 NO를 출력한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int sum =0;
        int c1=0, c2=0;
        for(int i=0;i<N;i++) {
            int num = Integer.parseInt(st.nextToken());
            sum+=num;
            c1+=num%2;
            c2+=num/2;
        }
        System.out.println(sum%3!=0 || c1>c2?"NO":"YES");
    }
}

🥇 결과

🎓 느낀점

코드는 몹시 간단하다! 하지만 수학 문제 답게 아이디어가 필요했다.