시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (하단 참고) | 512 MB | 170 | 27 | 20 | 29.412% |
Albert는 Alice의 가게에서 포장하여 우편으로 부치는 일을 도와주기로 했다. 물건을 포장하는 일은 번거롭지만 간단하다.
우선 길이가 B로 동일한 상자를 여러 개 준비한다 (몇 개 준비해야 충분한지 계산하는 것이 Albert의 일이다). 하루 동안 총 R대의 트럭이 공장에서 가게로 물건을 배달해오는데, 한 번에 한 대의 트럭에서 물건을 모두 배달 받은 후 다음 트럭에서 물건을 배달 받는 식으로 진행한다. 각 트럭은 모두 똑같이 n개의 물건을 배달하며, 각 물건에 1번부터 n번까지 고유한 번호가 붙어 있어서 이 순서대로 물건을 꺼내야만 한다.
i번째 물건의 길이를 v[i]라 하자.
아래 그림은 R = 4, n = 3 이고 v = [2, 2, 3]인 경우를 보여준다. 즉 각각의 트럭에 길이가 2, 2, 3인 물건이 실려있고, 이 순서로 (좌에서 우로) 물건을 꺼낸다고 생각하면 된다.
Albert는 이 물건들을 길이가 B인 상자에 순서대로 넣어서 잘 포장하여 목적지에 부치는 일을 도와주기로 했다. 단, 앞서 언급한대로 1번 트럭부터 R번 트럭까지, 그리고 각 트럭에서 물건을 번호 순서대로 꺼내서 넣어야만 한다.
예를 들어 B = 5 인 경우, 위 예제의 경우 상자가 총 여섯 개 필요하다. 아래 그림은 좌측부터 순서대로 여섯 개의 상자를 이용하여 Albert가 물건을 채운 모습을 나타낸다.
Albert는 트럭이 배달을 시작하기 전 미리 상자가 몇 개나 필요할지 계산해서 Alice에게 알려주어야 한다.
입력으로 n, B, R, 그리고 물건의 길이를 나타내는 v 값들이 주어졌을 때, 길이가 B인 상자가 총 몇 개 필요한지 계산해보자.
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어진다.
테스트 케이스의 첫 줄에 n, B, R이 주어진다. 둘째 줄에 물건의 길이를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
5 4 6 3 1 1 1 1 3 5 4 2 2 3 5 5 4 2 2 3 3 2 7 5 5 2 3 2 2 3 2 3 2 4000 12345678912345 1234 2345
2 6 12 18 12345678912345
예제 1: 총 12개의 물건이 있고, 각 물건의 길이가 1이다. 각 상자의 길이는 6이므로 상자 두 개가 필요하다.
예제 2: 본문에서 다루었다.
예제 3-4: 추가 설명 없음.
예제 5: R값의 범위에 주의하자.