3362번 - 수수께끼 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 161 | 90 | 69 | 58.974% |
문제
엘레오노라의 할머니 서차(Sercha)는 손녀, 손자들에게 수학 수수께끼를 내는 것을 좋아하십니다. 저번 가족여행에서는 이 문제를 내주셨습니다 :
"만약 어떤 가게에 K개의 상품을 팔고 있고 가격은 1에서 K라고 한다면, 내가 N개의 동전을 갖고 있고 그 동전은 A1,A2,. . .,AN이라고 한다. 나는 너무 늙어서 딱 그 가격에 최소 개수를 가져가고 싶어. 동전을 A1부터 차례대로 가져갈때, 동전을 몇 개 가져가면 최소 개수로 1부터 K까지의 가격을 지불할 수 있을까?"
엘레오노라는 몇 초 지나지 않고 대답했고, 생각했습다.
"이런 기본적인 알고리즘은 이제 쉽죠!"
엘레오노라를 도와줄 프로그램을 작성해 봅시다.
입력
첫 줄에는 테스트 케이스 수인 T가 주어집니다. 각 케이스의 첫째 줄에는 N(N≤100,000)과 K(K≤1,000,000)가 입력되고 둘째 줄에는 N개의 정수 동전 가치Ai(Ai≤100,000)가 주어집니다.
출력
각 테스트 케이스마다 서차 할머니께서 가져가셔야 하는 동전 개수를 출력하고 만약 N개를 다 가져가셔도 할 수 없으시다면 -1을 출력한다.
예제 입력 1
3 7 10 1 2 3 4 5 6 7 3 3 2 4 1 3 6 3 1 4
예제 출력 1
4 3 -1
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호