만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

나무 울타리

면접 대비

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

요약
주어진 길이의 판자 N개를 모두 한 번씩 사용해 높이 2인 직사각형 울타리를 겹치지 않게 만들 수 있는지 판별합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 수학, 구현
정답자
아직 제출이 없습니다

문제

빈센트는 최근 농장을 샀다. 그는 말과 염소를 키우며 은퇴 생활을 즐길 계획이다. 동물들이 빠져나가지 않도록 농장 둘레에 울타리를 세워야 한다. 다행히 울타리는 농장의 한 면에만 세우면 된다. 나머지 면은 자연 지형이 울타리 역할을 한다.

울타리의 높이는 정확히 2단위이고, 완전한 직사각형을 이루어야 한다. 왜 완전한 직사각형이어야 할까? 울타리 윗부분에 구멍이 있으면 말이 뛰어넘을 수 있다. 아랫부분에 구멍이 있으면 염소가 기어 나올 수 있다.

빈센트에게는 울타리를 만들 널빤지가 NN개 있다. ii번째 널빤지의 크기는 1×Li1 \times L_i이다. 널빤지는 완성된 울타리의 높이가 2이기만 하면 가로(1×Li1 \times L_i)로도, 세로(Li×1L_i \times 1)로도 놓을 수 있다.

빈센트는 매우 인색하다. 그는 가진 널빤지를 모두 사용하기를 고집하며, 완성된 울타리의 길이는 신경 쓰지 않는다. 널빤지끼리 겹치면 비효율적이라고 생각하므로 널빤지는 겹치면 안 된다.

입력

첫 줄에 널빤지의 개수를 나타내는 정수 NN(1≤N≤5001 \le N \le 500)이 주어진다. 다음 줄에는 각 널빤지의 길이를 나타내는 정수 LiL_i(1≤Li≤5001 \le L_i \le 500)가 NN개 주어진다.

출력

모든 조건을 만족하는 울타리를 만들 수 있으면 "YES", 없으면 "NO"(따옴표 제외)를 출력한다.

예제3

  1. 예제 1

    입력
    4
    2 5 1 4
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    2
    2 2
    
    예상 출력
    YES
    
  3. 예제 3

    입력
    4
    1 3 4 4
    
    예상 출력
    NO