사과나무

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 나무의 목표 높이가 주어질 때, 1만큼과 2만큼 자라는 두 물뿌리개를 매번 동시에 사용해 모든 나무를 정확히 그 높이로 만들 수 있는지 판정한다.

난이도: 보통10점 중 5점
유형: 그리디, 수학, 구현, 배열
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

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

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

출력

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

예제4

예제 1
입력
```
1
0
```
예상 출력
```
YES
```
예제 2
입력
```
2
4 3
```
예상 출력
```
NO
```
예제 3
입력
```
3
10000 1000 100
```
예상 출력
```
YES
```
예제 4
입력
```
5
1 3 1 3 1
```
예상 출력
```
NO
```