1 minute read

19539번 : 사과나무

문제 링크

https://www.acmicpc.net/problem/19539

문제 설명

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

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

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

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

입력

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

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

출력

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

문제 풀이

각각 1, 2만큼 성장시키는 물뿌리개를 동시에 사용해서 원하는 높이의 사과나무를 만드는 문제이다.

  1. 사과나무 높이의 합이 3의 배수여야 한다.
  2. 1만큼 성장시키는 물뿌리개와 2만큼 성장시키는 물뿌리개를 뿌리는 횟수를 세어 2만큼 성장시키는 물뿌리개를 쓰는 횟수가 1만큼 성장시키는 물뿌리개를 쓰는 횟수보다 크거나 같아야한다.
N = int(input())
arr = list(map(int, input().split()))

one, two = 0, 0

for tree in arr : 
    one += tree % 2
    two += tree // 2

if sum(arr) % 3 == 0 and two >= one :
    print("YES")
else : 
    print("NO")

Comments

You May Also Enjoy