시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 230 | 43 | 33 | 17.647% |
민식이는 새로운 퍼즐을 선물로 받았다. 보드는 다양한 길이의 여러개의 조각으로 이루어져 있다. 각 조각은 보드와 같은 폭을 가지고 있다. 퍼즐의 목표는 다른 조각을 더 이상 놓을 수 없게 적은 수의 조각을 놓는 것이다. 조각은 보드의 모서리에 걸치면 안되고, 각도를 비틀어도 안되며, 모든 조각은 서로 겹치면 안 된다. 그러나, 조각의 모서리는 서로 닿아도 된다. 조각과 조각 사이의 거리와, 조각과 보드의 모서리 사이의 거리는 꼭 정수가 아니어도 된다.
보드의 길이와 각 조각의 길이가 주어질 때, 퍼즐의 목표를 수행하는 프로그램을 작성하시오.
첫째 줄에 L과 조각의 수 N이 주어진다. L은 1,000보다 작거나 같은 자연수이고, N은 30보다 작거나 같은 자연수이다. 둘째 줄에는 각 조각의 길이가 주어진다. 각 조각의 길이는 100보다 작거나 같은 자연수이다.
첫째 줄에 문제의 정답을 출력한다.
36 5 1 1 5 5 5
4
9 2 1 8
1
37 5 1 1 5 5 5
5
18 6 2 2 2 9 9 10
2
1 3 2 3 4
0
703 18 73 76 90 42 84 13 57 88 80 45 80 1 78 41 73 40 97 42
7