Informatica Online Judge

  CD녹음하기 [1164 / 048C]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 12


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[USACO]

Background

경곽이는 이번에 자기가 좋아하는 곡들을 이용해서 CD를 몇 장 만들기로 했다.

모두 n곡의 노래가 준비되어 있으며, m장의 CD 에 가능한 많은 곡을 녹음해야 한다.

각 CD는 모두 t분을 녹음할 수 있다.

녹음할 때 반드시 다음 조건을 지켜야 한다.

각 CD에 t분 이하로만 녹음할 수 있다.
한 곡이 2개 이상의 CD에 나눠서 녹음할 수 없다.
1-m까지의 CD 내에서는 입력된 순서대로 녹음되어야 한다.

이 조건을 만족하면서 녹음하려고 할 때, m장의 CD에 최대한 녹음할 수 있는 곡의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, t, m이 공백으로 구분되어 입력된다.

두 번째 줄에는 n개의 각 곡의 길이가 공백으로 구분되어 입력된다.

모든 입력값은 1이상 20이하의 값이다.

Output

조건을 만족하는 최대 곡의 수를 출력한다.

IO Example

입력
4 5 2
4 3 4 2

출력
3

* 설명 : 4곡이 있으며, 5분을 녹음할 수 있는 CD가 2장 있을 때, 첫 번째 CD에 두 번째와 네번째 곡을 녹음하면 5분 1장을 채울 수 있으며, 두 번째 CD는 세 번째 곡을 녹음하면 4분으로 모두 3곡을 녹음할 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]