[PS] 백준 #19539. 사과나무

문제 정보

• 난이도: 실버 I
• 문제 주소: https://www.acmicpc.net/problem/19539
• 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디

 

문제

이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 $1$번부터 $N$번까지 심었다. 이 나무들의 초기 높이는 모두 $0$이다.

사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 $2$개를 준비했다. 한 물뿌리개는 나무 하나를 $1$만큼 성장시키고, 다른 물뿌리개는 나무 하나를 $2$만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 $3$만큼 키울 수도 있다.

물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지 못할 수도 있기 때문이다.

이하는 이제 프로그램을 다시 수정하느라 바쁘기 때문에, 두 물뿌리개를 이용해 갊자가 알려준 사과나무의 배치를 만들 수 있는지의 여부를 판단하는 과정은 여러분의 몫이 되었다.

 

나의 풀이

처음에는 3으로 나눈 나머지를 1, 2인 경우만 생각해서 코드를 짰더니 한참 헤맸다. 처음에 생각한 아이디어는 이랬다.

1. 3의 배수는 항상 물을 뿌릴 수 있으므로 처음부터 후보에서 제외하기
2. 3보다 큰 3k+1과 3k+2를 한 세트로 묶어서 없애주기
3. 남은 3k+1 / 3k+2들 중에서 3개 이상 남은게 있으면 걔네들끼리 묶어서 없애주기
4. 3보다 작은 애들은 1과 2끼리만 묶어서 없애주기
5. 위 과정에서 없애지 못한게 있으면 NO, 아니면 YES 출력하기

그러나 이 아이디어는 두번이나 틀렸습니다가 떠서 아예 접근을 잘못한건가 싶었다.. 한참을 고민해봐도 다른 방법이 보이지 않아서 구글링을 해보니 2로 나눈 몫이 힌트라는걸 알게 되었다. 물뿌리개를 한번 뿌릴 때 2만큼 자라게 해야 하므로 2만큼 자란 횟수는 총 자란 횟수랑 같다. 즉, 2만큼 성장하는 횟수가 물을 주는 횟수 이상이면 YES이다. 물론 처음부터 총합이 3의 배수가 아닌 경우는 NO를 출력해주면 된다. 

#include <bits/stdc++.h>

using namespace std;

// 14% 틀렸습니다 -> mod1, mod2 로만 접근
// 2 자라게 하는 횟수 == 총 자라는 횟수
// 즉, 높이의 합이 3의 배수이면서, 2만큼 성장을 X번 시킬 수 있다면 "YES"
// 따라서 2로 나눈 몫의 개수가 (전체 높이 / 3 == 물 주는 횟수) 이상이면 된다.

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

    int n; cin >> n; 
    int height = 0, total = 0;

    while (n--) {
        int h; cin >> h;
        height += h / 2;
        total += h;
    }
    
    if (total % 3 != 0) {
        cout << "NO"; return 0;
    }

    // total 이 3의 배수일 경우
    // 2를 줄 수 있는 경우가 전체 물 주는 횟수보다 많으면 YES
    if (height >= total / 3) cout << "YES";
    else cout << "NO";
    return 0;
}