| 정해진 시간 안에 최대한 많은 과제하기 |
|---|
정해진 시간 안에 최대한 많은 과제를 하고자 한다. 그런데 각각의 과제를 완료하려면 일정 양의 시간이 필요하며, 한 번에 하나의 과제만 수행할 수 있다. 수행하는 과제의 순서는 자유롭게 선택할 수 있다. 정해진 시간 안에 완료 가능한 최대 과제 수를 출력하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
입력 파일의 첫 번째 줄에 과제를 수행할 수 있는 전체 시간 T(0<=T<=100000)분이 주어진다. 두 번째 줄에 과제 수 C(0<=C<=100)가 주어진다. 세 번째 줄부터 총 C개 줄에 걸쳐서 각각의 과제를 수행하는데 필요한 시간들이 분 단위로 주어진다. 각각의 과제를 수행하는데 필요한 시간은 최대 100000 분이다. | |
| 출력 | |
|---|---|
주어진 전체 시간 T 내에 완료 가능한 최대 과제수를 출력한다. ※ 예시 1 : 주어진 전체 시간은 6분이다. 과제 수는 3개이며 첫 번째 과제는 3분, 두 번째 과제는 6분, 세 번째 과제는 3분이 필요하다. 정답은 2이다. 왜냐하면 전체 시간 6분 안에 완료할 수 있는 과제의 최대수는 2개, 즉, 첫 번째 과제와 세 번째 과제를 완료할 수 있다. 예시 2 : 세 번째, 네 번째, 다섯 번째 과제를 6분 내에 완료할 수 있다. 따라서 6분 내에서 4개 이상의 과제를 완료할 수는 없다.
예시 1 : | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 6 3 3 6 3 | |
| 출력 | 2 | ||