[백준 - 19539] 실버1 사과나무 (그리디)

www.acmicpc.net/problem/19539

19539번: 사과나무

 

1. 유형

그리디

 

2. 풀이법

사과나무 크기의 합이 3의 배수이다

 

홀수의 갯수가 전체합/3보다 작아야한다.

 

예를 들어 {1 2 1 2}는 가능하다.

 

하지만 {3 1 1 1}는 불가능하다. 한 턴에 물뿌리게를 다 써야하니깐....

 

그래서 두번째 조건이 들어가야 한다

 

3. 코드

import java.util.Scanner;

public class back_19539사과나무 {
	public static void main(String[] args) {
		 Scanner sc = new Scanner(System.in);
		 int n = sc.nextInt();
		 int tmp;
		 int sum = 0;
		 int num=0;
		 for (int i = 0; i < n; i++) {
			tmp= sc.nextInt();
			sum += tmp;
			if(tmp%2==1) {
				num++;
			}
		}
		if(sum%3==0 && num<=sum/3) {
			System.out.println("YES");
		}else
			System.out.println("NO");
	}
}