만드는 중입니다

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

Another Brick in the Wall

면접 대비

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

요약
벽돌 더미를 순서대로 사용해 너비 w인 층을 h개 쌓을 때, 남은 벽돌이 부족하지 않고 모든 층을 정확히 채울 수 있는지 판단한다.
난이도

쉬움10점 중 3점

유형
시뮬레이션, 구현, 배열, 그리디
정답자
아직 제출이 없습니다

문제

예전에 라르스라고 불리던 건설 노동자는 높이가 11이고 길이는 제각각인 벽돌을 잔뜩 쌓아 두었다. 라르스는 이 벽돌로 너비 ww, 높이 hh인 벽을 쌓으려고 한다. 부분집합 합 문제가 NP-난해라는 사실을 알기 때문에 라르스는 벽돌 배치를 최적화하지 않는다. 그냥 더미에 놓인 순서대로 벽돌을 집어서 쌓고, 잘 맞기를 바랄 뿐이다.

라르스는 첫 번째 층을 왼쪽에서 오른쪽으로 채운다. 그 층이 꽉 차면 두 번째 층으로 올라가 같은 방식으로 채우고, 그다음 층도 마찬가지로 채운다. 벽돌은 돌리지 않고 눕힌 채로만 놓으므로 벽돌 하나가 두 층에 걸치는 일은 없다. 집어 든 벽돌이 지금 층에 남은 자리보다 길어서 놓을 수 없으면, 라르스는 그 층을 끝내지 못한 채 짜증을 내고 떠난다. 벽을 다 쌓은 뒤에 벽돌이 남는 것은 상관없다.

어제 라르스는 마지막 층에 이르러서야 벽을 완성할 수 없다는 사실을 깨닫고, 몹시 짜증이 나서 벽을 허물어 버렸다. 오늘 라르스가 들고 온 벽돌 더미로 벽을 완성할 수 있는지 알려주자.

입력

첫째 줄에 세 정수 hh, ww, nn (1≤h≤1001 \le h \le 100, 1≤w≤1001 \le w \le 100, 1≤n≤100001 \le n \le 10000)이 주어진다. 각각 벽의 높이, 벽의 너비, 벽돌의 개수이다.

둘째 줄에 벽돌의 길이를 나타내는 정수 nn개 xix_i (1≤xi≤101 \le x_i \le 10)가 더미에 쌓인 순서대로 주어진다.

출력

라르스가 벽을 완성하면 YES를, 그렇지 않으면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    2 10 7
    5 5 5 5 5 5 5
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    2 10 7
    5 5 5 3 5 2 2
    
    예상 출력
    NO