23026번 - 물건 포장하기
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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가 물건을 채운 모습을 나타낸다.
- 먼저, 1번 트럭에서 1번과 2번 물건을 꺼내 첫 번째 상자에 담는다. 3번 물건을 넣기에는 상자의 길이가 모자라므로 두 번째 상자가 필요하다.
- 두 번째 상자에는 1번 트럭에서 꺼낸 3번 물건과 2번 트럭에서 꺼낸 1번 물건을 넣을 수 있다.
- 세 번째 상자에는 2번 트럭에서 꺼낸 2번과 3번 물건을 넣을 수 있다.
- 네 번째 상자에는 3번 트럭에서 1번과 2번 물건을 넣을 수 있다.
- 다섯 번째 상자에는 3번 트럭에서 꺼낸 3번 물건과 4번 트럭에서 꺼낸 1번 물건을 넣을 수 있다.
- 마지막 여섯 번째 상자에는 4번 트럭에서 2번과 3번 물건을 넣을 수 있다.
- 따라서 이 경우 총 여섯 개의 상자가 필요하다.
Albert는 트럭이 배달을 시작하기 전 미리 상자가 몇 개나 필요할지 계산해서 Alice에게 알려주어야 한다.
입력으로 n, B, R, 그리고 물건의 길이를 나타내는 v 값들이 주어졌을 때, 길이가 B인 상자가 총 몇 개 필요한지 계산해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어진다.
테스트 케이스의 첫 줄에 n, B, R이 주어진다. 둘째 줄에 물건의 길이를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n, B ≤ 4,000
- (각 물건 i에 대하여) 1 ≤ v[i] ≤ B
- 1 ≤ R ≤ 1015
예제 입력 1
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
예제 출력 1
2 6 12 18 12345678912345
예제 1: 총 12개의 물건이 있고, 각 물건의 길이가 1이다. 각 상자의 길이는 6이므로 상자 두 개가 필요하다.
예제 2: 본문에서 다루었다.
예제 3-4: 추가 설명 없음.
예제 5: R값의 범위에 주의하자.
시간 제한
- Java 8: 2 초
- PyPy3: 3 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호