[백준 19539번] 파이썬 - 사과나무

백준 19539 - 사과나무

시간 제한 1초(추가 시간 없음), 메모리 제한 1024MB

# 조건

• 이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 1$1$번부터 N번까지 심었다.
  • 이 나무들의 초기 높이는 모두 0이다.
• 사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 2개를 준비했다.
• 한 물뿌리개는 나무 하나를 1만큼 성장시키고, 다른 물뿌리개는 나무 하나를 2만큼 성장시킨다.
• 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다.
• 두 물뿌리개를 한 나무에 사용하여 3만큼 키울 수도 있다.
• 물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다.
• 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다.
• 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지 못할 수도 있기 때문이다.
• 이하는 이제 프로그램을 다시 수정하느라 바쁘기 때문에, 두 물뿌리개를 이용해 갊자가 알려준 사과나무의 배치를 만들 수 있는지의 여부를 판단하는 과정은 여러분의 몫이 되었다.

입력

• 첫 번째 줄에는 자연수 N이 주어진다. (1≤N≤100 000)
  • 이는 이하가 뒷뜰에 심은 사과나무의 개수를 뜻한다.
• 두 번째 줄에는 N개의 정수 ℎ1,ℎ2,⋯,hN이 공백으로 구분되어 주어진다. (0≤ℎ≤10 000)
  • h_i는 갊자가 바라는 i번째 나무의 높이이다.

출력

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

# 접근 방법

• 모든 사과나무를 갊자가 원하는 높이로 키우기 위해서는 동시에 물을 줄 수 있는 경우를 체크해야 된다.
  • 한 번에 줄 수 있는 경우는 한 나무에 3을 주거나, 동시에 2개의 나무에 1과 2를 주는 것이다.
• 따라서 모든 나무의 합이 3의 배수가 아니라면 갊자의 바램을 이룰 수 없다.
• 만약 모든 나무의 합이 3의 배수인 경우 아래 조건을 체크해준다.
  • 모든 나무를 2로 나눈 몫의 합과 2로 나눈 나머지를 구해준다.
  • 2로 나눈 나머지의 경우 => 모든 나무가 반드시 1로 성장시켜야 되는 횟수이고
  • 이 때, 2로 작업할 수 있는 일수가 2로 나눈 나머지 보다 작다면 불가능 하기 때문이다.
• 이후, (2로 나눈 몫의 합 - 2로 나눈 나머지의 합)이 3의 배수이고, 2로 나눈 몫의 합이 2로 나눈 나머지의 합보다 크다면 갊자의 바램을 이룰 수 있다.
  • 오직 2로만 성장시킬 수 있는 횟수가 3의 배수라면, 1과 2로 나눌 수 있으므로 가능하다!

import sys
input = sys.stdin.readline

N = int(input())
nums = [*map(int, input().split())]
val1 = sum(i%2 for i in nums)
val2 = sum(i//2 for i in nums)
print('YES' if not (val2-val1) % 3 and val2 >= val1 else 'NO')