UCPC 2020 예선 H / 사과나무 - 19539

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    int sum = 0;
    int u;
    int cnt = 0;
    for(int i = 0; i<N; ++i) {
        cin >> u;
        sum += u;
        cnt += (u/2);
    }
    if(sum%3 == 0 && sum/3 <= cnt) cout << "YES";
    else cout << "NO";
}

 

 

 

 

 

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

19539번: 사과나무

 

 

 

 

 

사과나무 - 19539

한번 물을 뿌리면 전체 나무의 길이는 3씩 증가합니다.

따라서 전체 나무길이의 총합은 무조건 3의 배수 입니다.

전체 나무길이의 총합이 3의 배수이고, 우리의 방법으로 만들수 있는 경우라면,

2/1 를 a번 뿌리고, 3을 b번 뿌려 완성할 수 있습니다.( 3*(a+b) 는 전체 나무길이의 총합)

 

3을 b번 뿌리는 것은 각각 나무의 길이가 3의 배수라는 뜻 입니다.

서로 다른 나무에 3을 각각 하는것은 2/1을 엇갈려 두번 뿌리는것으로 만들 수 있습니다.

즉, 3을 b번 뿌리는 것은 2/1을 적절하게 뿌리고(안 뿌릴 수도 있습니다.), 마지막 나무에 부족한 만큼 3을 채운 것으로 얼마든지 변형이 가능합니다.

 

 

즉 이로인해 만들 수 있는 경우라면 최대한 a의 개수를 늘리고 b를 최소한으로 줄일 수 있습니다.

이것의 의미는 만들 수 있는 모든 경우에 대해서, 2/1을 적절하게 뿌린다면, 오직 하나의 나무에만 3을 계속 더해 완성할 수 있다 를 의미합니다.

 

2/1을 a번 뿌리는 것을 이렇게 나누어 보겠습니다.(+1은 최적의 선택으로 자동으로 어딘가에 채워집니다)

1번나무에 +2로 a1번,

2번나무에 +2로 a2번, 

...

n번나무에 +2로 a3번

이렇게 수행하고 나면 위의 나무중 하나에 3을 b번만 뿌리면 됩니다.

 

위의 방법을 동치인 수학식으로 만들 수 있습니다.

바로 각각의 나무의 크기 / 2 의 몫을 모두 더한 다음,

그 합이 >= (a+b) 이다

라는 수식과 동치입니다.

따라서 저희는 전체 나무길이의 총합이 3의 배수이고, 각각의 나무길이를 2로 나눈 몫의 합이 총합을 3으로 나눈 몫의 합보다 크거나 같으면 YES이고, 아닌 경우엔 NO라는 것을 알 수 있습니다.