백준 사과나무(19539)

사과나무

1. 힌트

1) $2$ 물뿌리개와 $1$물뿌리개를 동시에 사용해야한다는 조건을 무시하고 사과나무의 배치를 만들어 봅시다.

2) 1)에서 사과나무의 배치를 만들어낸 방법을 약간 수정해봅시다. $2$ 물뿌리개를 사용하는 것은 $1$짜리 물뿌리개를 $2$번 사용하는 것으로 바꿀 수 있습니다.

3) 따라서 1)에서 사과나무 배치를 만들 때, $2$ 물뿌리개를 최대한 많이 사용합시다. 그리고, $2$ 물뿌리개와 $1$ 물뿌리개를 사용한 횟수가 같아지도록 바꿔봅시다.

2. 접근

사과나무의 배치 $h_1, h_2, \cdots, h_n$을 만들어내는 방법이 존재한다면 다음과 같이 $2$와 $1$의 합으로 표현할 수 있습니다.

그런데, 정답이 하나만 존재하는 것은 아닙니다. 다음과 같이도 표현할 수 있습니다.

기존의 정답에서 $2$를 $1 + 1$로 바꾸고 $1 + 1$을 $2$로 바꾸더라도 여전히 정답입니다.

$2$는 언제나 $1+1$로 바꿀 수 있는 반면 $1 + 1$은 서로 다른 수에 있을 수도 있기 때문에 언제나 $2$로 만들 순 없습니다. 그렇다면 $2$ 물뿌리개와 $1$ 물뿌리개를 같은 횟수 사용한다는 조건을 무시하고, $2$ 물뿌리개를 최대한 많이 사용해서 표현해 보겠습니다. 이렇게 표현하는 것은 언제나 가능합니다.

$2$는 $5$번, $1$은 $2$번 사용했습니다. 여기서 $2$를 $1 + 1$로 한 번 바꿀 수 있습니다. $2$는 $4$번, $1$은 $4$번 사용하니 문제의 조건을 만족합니다.

위와 같이 조건을 무시하고 표현했을 때, 사용한 $2$ 물뿌리개의 횟수를 $a$, $1$ 물뿌리개의 횟수를 $b$라고 하면, $2$를 $1 + 1$로 바꿀 때마다 $a - b$가 $3$씩 줄어드는 것을 알 수 있습니다. 따라서 $a \ge b$를 만족하면서 $a$와 $b$의 차가 $3$으로 나누어 떨어져야 정답이 존재함을 알 수 있습니다.

위 방법의 정당성을 증명하겠습니다.

위와 같은 어떤 임의의 해가 존재할 때, 그 해에서 $1 + 1$을 $2$로 바꾸어주는 과정을 적용하면 우리가 조건을 무시하고 $2$ 물뿌리개를 최대한 많이 사용해서 표현한 방법과 같아지는 것을 알 수 있습니다.

이 상태에서 $2$를 $1+1$로 바꿔주는 과정을 적용하는 것은 위 과정을 거꾸로 적용한 것과 같으므로 반드시 해를 찾을 수 있습니다.

3. 구현

n = int(input())
h = list(map(int, input().split()))

a, b = 0, 0

for i in range(n):
    a += h[i] // 2
    b += h[i] % 2

if a >= b and (a - b) % 3 == 0:
    print('YES')
else:
    print('NO')