백준 BOJ 19539 - 사과나무

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

19539번: 사과나무

굉장히 빠르게 풀어내서 만족스러운 문제.

일단 쉽게 관찰할 수 있는 첫번째 특징으로,

입력으로 들어온 $h_k$ 들의 합 $sum$ 이 반드시 3의 배수여야만 한다.

두 물뿌리개를 동시에 사용하면 물이 3만큼 뿌려지게 되기 때문이다.

 

예제 입력 4로 설명해주고 있는 또다른 조건의 하나로,

이 조건으로 인해 골드5라는 티어를 배정받지 않았나 싶다.

 

나무 하나를 2만큼 성장시키는 물뿌리개는 아무리 뿌려도

짝수 높이만큼의 나무를 만들 수 있기 때문에,

홀수 높이를 만들기 위해서는 반드시 1 물뿌리개를 뿌려줘야 한다.

이렇게 반드시 뿌려줘야만 하는 == 홀수인 $h_k$들의 갯수를 세준 다음에,

 

각 $h_k$에 대해서

2 물뿌리개의 사용 횟수 $cnt$ 도 세줘서

이 둘을 비교해줘야 한다.

 

만일 2 물뿌리개 사용 횟수보다 1 물뿌리개를 사용해야만 하는 횟수가 많다면

정답이 되는 경우의 수가 없으나,

2 물뿌리개의 사용 횟수보다 1 물뿌리개를 사용해야만 하는 횟수가 적다면

2 물뿌리개 횟수의 일부를 1 물뿌리개로 대신 사용함으로써

정답을 만들어낼 수 있기 때문이다.

 

이 두가지 조건을 만족하는 경우 YES를 출력하게

소스코드를 작성하면 된다.

 

입력 범위가 제법 크기 때문에

$sum$ 이 int범위를 넘어갈 수도 있지 싶다.

안전하게 long long 형으로 선언해줬다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int arr[123456];

ll one=0;
ll two=0;
ll sum=0;

int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> arr[i];
		one += (arr[i]%2);
		two += (arr[i]/2);
		sum += arr[i];
	}
	
	if(sum%3 != 0 || one > two) cout << "NO";
	else cout << "YES";
	return 0;
}