[백준, BOJ] 19539 - 사과나무

1. Question

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

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

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

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

1.1 Input

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

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

1.2 Output

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

1.3 Example

입력	출력
1 0	YES
2 4 3	NO
3 10000 1000 100	YES
5 1 3 1 3 1	NO

2. Approach

규칙성을 간파하기가 조금 난해한 문제다.

대전제는 1칸 짜리 물뿌리개와 2칸 짜리 물뿌리개를 어떻게 분배하냐는건데, 이 두 경우는 2로 나눴을 때의 몫과 나머지의 합으로 알아낼 수 있다.

예를 들어, 3 3 3 이렇게 입력이 들어오면 몫의 합이 3, 나머지의 합이 3이므로 알맞게 분배할 수 있다.

하지만, 1 3 1 3 1의 경우에는 몫의 합이 2, 나머지의 합이 5이므로 알맞게 분배할 수 없다.

10000, 1000, 100의 경우에는 몫의 합과 나머지의 합이 같지 않은데, 이 경우에는 2칸 짜리 물뿌리개를 한번 쓰는 대신, 1칸 짜리 물뿌리개를 두번 쓰는 것으로 생각할 수 있다. 이렇게 물뿌리개를 대체하는 횟수를 x라고 하면,

다음과 같은 식이 성립한다.

$$d - x = r + 2x$$

$$x = {d - r \over 3}$$

x는 정수여야하고, 동시에 음수이면 안된다. 

x의 조건을 판별하면서 d와 r이 같은 경우까지 확인하면 끝.

3. Submission

4. Code

import sys
rl = sys.stdin.readline

N = int(rl())

heights = list(map(int, rl().split()))

d = 0
r = 0

for i in heights:
    d += i // 2
    r += i % 2
    
if (d - r) % 3 == 0 and d >= r:
    print("YES")
else:
    print("NO")