백준 사과나무(19539)

axiom·2021년 7월 17일

사과나무

1. 힌트

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

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

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

2. 접근

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

h_1, h_2, h_3 = \{6,5,1\} =\{(2+2+1+1), (2+2+1), (1)\}

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

\{(2+2+2), (2+1+1+1),(1)\}

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

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

h_1, h_2, h_3 ={6,5,1} = \{(2+2+2)+(2+2+1)+(1)\}

$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$ 으로 나누어 떨어져야 정답이 존재함을 알 수 있습니다.

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

h_1, h_2, h_3 = \{6,5,1\} =\{(2+2+1+1), (2+2+1), (1)\}

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

h_1, h_2, h_3 = \{6,5,1\} =\{(2+2+2), (2+2+1), (1)\}

이 상태에서 $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')