[ BOJ ] 19539 : 사과나무 ( GOLD 5 ) / Python

문제

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

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

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

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

입력

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

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

출력

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

풀이 과정

먼저, 모든 나무에 3만큼 물뿌리개를 먼저 뿌렸을 때 남은 성장 높이가 1이거나 2인 나무들 (원하는 높이를 3으로 나누었을 때의 나머지가 1이거나 2인 나무들)의 개수를 센다.

 

- 남은 성장 높이가 1인 나무들의 개수보다 남은 성장 높이가 2인 나무들의 개수가 작을 때 : 물뿌리개 2개를 골고루 사용하면 남은 성장 높이가 2인 나무들은 없어지고 남은 성장 높이가 1인 나무들만 남게 되는데, 물뿌리개를 1개만 사용할 수 없으므로 원하는 높이대로 만들 수 없다. ( NO )

 

- 남은 성장 높이가 1인 나무들의 개수와 남은 성장 높이가 2인 나무들의 개수가 같을 때 : 물뿌리개 2개를 골고루 사용하여 정확히 원하는 높이대로 만들 수 있다. ( YES )

 

- 남은 성장 높이가 1인 나무들의 개수보다 남은 성장 높이가 2인 나무들의 개수가 클 때 : 남은 성장 높이가 2인 나무들을 3개씩 사용하면 2 - 1 1 - 2 방식으로 물뿌리개를 배분할 수 있어 원하는 높이대로 만들 수 있다. 따라서 물뿌리개 2개를 골고루 사용한 후 남은 성장 높이가 2인 나무들만 남았을 때, 남은 성장 높이가 2인 나무들의 개수가 3의 배수라면 원하는 높이대로 만들 수 있다.

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))

cnt = [0, 0]
for a in arr:
    cnt[0] += a // 2
    cnt[1] += a % 2

if cnt[0] - cnt[1] >= 0 and (cnt[0] - cnt[1]) % 3 == 0: print('YES')
else: print('NO')