[BOJ/백준][Gold5] 19539 : 사과나무 (C++)

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

19539번: 사과나무

 

 

[난이도] Gold5
[유형] 수학

[풀이]
1과 2가 무조건 동시에 사용되어야 하므로, 전체 수열의 합이 3의 배수여야 하고
(전체 수열의 합 / 3) = (물뿌리개를 사용해야 하는 횟수) = (2를 사용해야 하는 횟수) 이므로
1~N 사과나무들의 2로 나눈 몫의 합이 위의 (2를 사용해야 하는 횟수) 이상이어야 합니다.

이것을 만족하지 못하는 조건은 다음과 같이 표현이 가능합니다.
cnt : 2로 나눈 몫의 합
if(sum%3||cnt<sum/3) {
    puts("NO");
    return 0;
}

 

 

#include <cstdio>
int N,a[100000],sum,cnt;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&a[i]);
        sum+=a[i];
        cnt+=a[i]/2;
    }
    if(sum%3||cnt<sum/3) {
        puts("NO");
        return 0;
    }
    puts("YES");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/19539.cpp