티스토리 뷰

백준/골드

[백준 19539번] 사과나무 (C++)

게임개발기원 2025. 6. 22. 22:56

문제 링크 : https://www.acmicpc.net/problem/19539

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int sum = 0;
    int cnt2 = 0;

    for (int i = 0; i < n; i++) 
    {
        int h;
        cin >> h;
        sum += h; 
        cnt2 += h / 2; //다른 물뿌리개 가능 횟수
    }

    if (sum % 3 != 0 || cnt2 < sum / 3) cout << "NO";
    else cout << "YES";
    return 0;
}

 

기본적으로 나무 하나를 1만큼 성장시키거나, 2만큼 성장시키기에 한 번에 3만큼 성장시킨다는 것을 알 수 있다.

따라서 나무 높이의 합산이 3의 배수여야만 물뿌리개를 모두 알맞게 사용할 수가 있다.

 

하지만 3의 배수를 체크하는 것만으로는 부족하다.

아래의 예시의 경우 3의 배수이지만, 2만큼 성장시키는 물뿌리개의 사용이 불가능한 케이스이다.

1 1 1 3 3 3

 

따라서 추가적으로 2만큼 성장시키는 물뿌리개의 가능 회수 또한 체크하여야 한다.

이를 위해 입력받은 높이에 대해 2로 나누어 해당 물뿌리개 사용 가능 회수를 카운팅한다.

이렇게 구한 회수는 총 물 뿌리개 사용 회수라고 할 수 있는 sum/3의 값보다 작으면 균형이 맞지 않아 불가능한 케이스므로 NO를 출력한다.

'백준 > 골드' 카테고리의 다른 글

[백준 28069번] 김밥천국의 계단 (C++)  (0) 2025.05.08
[백준 10422번] 괄호 (C++)  (0) 2025.05.07
[백준 1253번] 좋다 (C++)  (0) 2025.05.04
[백준 2877번] 4와 7 (C++)  (0) 2025.04.30
[백준 1790번] 수 이어 쓰기 2 (C++)  (0) 2025.04.29
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함