시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 10185 | 4244 | 3157 | 43.282% |
아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.
각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.
마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.
예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.
보내는 마을 | 받는 마을 | 박스 개수 |
---|---|---|
1 | 2 | 10 |
1 | 3 | 20 |
1 | 4 | 30 |
2 | 3 | 10 |
2 | 4 | 20 |
3 | 4 | 20 |
이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.
(1) 1번 마을에 도착하면
보내는 마을 | 받는 마을 | 박스 개수 |
---|---|---|
1 | 2 | 10 |
1 | 3 | 20 |
1 | 4 | 10 |
(2) 2번 마을에 도착하면
보내는 마을 | 받는 마을 | 박스 개수 |
---|---|---|
2 | 3 | 10 |
(3) 3번 마을에 도착하면
보내는 마을 | 받는 마을 | 박스 개수 |
---|---|---|
3 | 4 | 20 |
(4) 4번 마을에 도착하면
위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.
입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.
트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | 보내는 마을번호는 모두 1, N ≤ 20 |
2 | 17 | 받는 마을번호는 N-1 또는 N, 3 ≤ N ≤ 20 |
3 | 20 | N ≤ 5, M ≤ 5, C ≤ 10 |
4 | 23 | N ≤ 100, M ≤ 1,000, C ≤ 2,000 |
5 | 25 | 추가적인 제약조건은 없다. |
4 40 6 3 4 20 1 2 10 1 3 20 1 4 30 2 3 10 2 4 20
70
6 60 5 1 2 30 2 5 70 5 6 60 3 4 40 1 6 40
150