BOJ 19539번 사과나무 파이썬

문제

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

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

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

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

입력

첫 번째 줄에는 자연수 N$N$이 주어진다. (1 ≤ N ≤ 100,000) 이는 이하가 뒷뜰에 심은 사과나무의 개수를 뜻한다.

두 번째 줄에는 N개의 정수 h1,h2, ..., hn이 공백으로 구분되어 주어진다. (0≤hi≤10,000) hi는 갊자가 바라는 i번째 나무의 높이이다.

출력

첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
s = list(map(int,input().split()))
total = sum(s)

if total % 3 != 0 :
    print('NO')
else:
    cnt = 0
    days = total // 3 
    
    for i in range(n):
        cnt+=s[i] // 2
        
    if cnt>=days:
        print('YES')
    else:
        print('NO')

풀이방식

일단은 YES가 나오기 위한 첫번째 조건은, 전체 길이 합이 3으로 나눠떨어지는 것이다.

1만큼 자라는 분무기도 있고, 2만큼 자라는 분무기가 있지만, 문제에 따르면 물을 ‘한 나무에 3만큼 몰아서’ 주던, 아니면 ‘한 나무에 1 다른 나무에 2’, 이렇게 나눠서 주던 매번 3만큼 주는 사실은 변하지 않기 때문이다.

그래서 3으로 나눠떨어지지 않으면 빼박 NO이다.

하지만 길이 총합이 3으로 나눠떨어진다고 해서, 무조건 YES가 아니라 한 조건이 더 갖추어져야 한다.

어떤 경우에던, (1 분무기와 2 분무기를 동시에 사용하거나, 동시에 한 나무에만 3만큼 몰아서 주거나), 한번 물을 줄 때 어떤 나무 ‘하나’ 이상은 꼭 2 혹은 3 이상의 분무기로 물을 받아야 한다.

따라서 예를 들어 1만큼 자라야 하는 나무가 3개 있어서 총합이 3으로 나눠떨어지더라도, 이 세 나무 중 어떤 나무도 2 혹은 3 이상의 분무기를 받을 수 없기 때문에 NO이다.

그래서 정리하자면, 일단은 길이의 총합이 3으로 나눠떨어지는지 보고 (조건 1 ), 만약 그렇다면, 배열을 돌면서 2 이상인 값의 개수가, 길이 총합을 3으로 나눈 값보다 같거나 큰지 보면 된다. (조건 2)