| 다리 건너기 실험 |
|---|
열차가 지나는 다리를 건설하는 충북건설회사는 최근에 자신들이 건설한 다리의 견고함을 확인하고자 다리 위로 KTX 열차가 지나는 실험을 하고자 한다. 다리의 길이는 40m이고, KTX 열차의 각 칸은 10m, 각 칸의 무게는 서로 다르다. 열차가 다리를 건너게 되면 열차의 4칸이 다리를 지나게 되고, 편의상 다리의 경계선에서 1개 칸이 걸치는 경우는 없다고 가정한다. 그런데, 다리 위에 있는 칸들의 무게의 총합이 다리가 견딜 수 있는 무게보다 더 무거우면 다리가 무너지게 된다. 충북건설회사는 이 실험을 통해 자신들이 건설한 다리를 무사히 건널 수 있는 KTX 열차의 칸 수를 결정하여 철도청에 통보하려고 한다. 다리가 견딜 수 있는 무게와 KTX 열차의 각 칸의 무게가 주어질 때 다리를 건널 수 있는 열차의 최대 칸 수를 계산하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
입력 파일의 첫 번째 줄에 다리가 견딜 수 있는 최대무게 W(1<=W<=100000)가 주어진다. 두 번째 줄에 열차의 칸 수 N(1<=N<=100000)이 주어진다. 그 다음 N개의 줄에 각 칸의 무게 wi가(1<=i<=N, 1<=wi<=100000) 순서대로 주어진다. 따라서, KTX 열차의 각 칸의 순서를 임의로 변경할 수 없으며 항상 1번째 칸부터 i번째(1<=i<=N) 칸까지 다리를 건널 수 있다. | |
| 출력 | |
|---|---|
첫 번째 줄에 다리를 건널 수 있는 최대 칸 수를 출력한다. ※ 예시 1 : 처음 4칸의 총 무게는 50+30+10+10=100이므로 다리가 견딜 수 있다. 처음 한 칸이 다리를 완전히 건너면 다리 위에는 그 다음 4칸이 놓여 있게 되고 총 무게는 30+10+10++40=90이므로 다리가 견디기에 충분하다. 그러나 열차의 마지막 4칸이 다리 위에 놓이게 되면 다리가 무너진다. 왜냐하면 10+10+40+50=110이고 이 무게는 다리가 견딜 수 없기 때문이다. 따라서 충북건설회사는 철도청에게 ‘처음 5개의 칸만 다리를 건널 수 있기 때문에, 6번째 칸 앞에서 열차를 분리해야 한다’고 통보하였다. ※ 예시 2 : 열차의 첫 번째 칸의 무게가 150으로 다리가 바로 무너지기 때문에 열차의 어떠한 칸들도 다리를 건널 수 없다. 충북건설회사는 철도청에 ‘이 열차는 첫 번째 칸이 너무 무거워서 어떠한 칸도 다리를 건널 수 없다’고 통보하였다(KTX 열차의 각 칸의 순서를 변경할 수 없음을 유념하라). | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 100 6 50 30 10 10 40 50 | |
| 출력 | 5 | ||
| 2 | 입력 | 100 3 150 1 1 | |
| 출력 | 0 | ||