5444번 - 시리얼 넘버 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 268 | 102 | 81 | 38.208% |
문제
위대한 기타리스트 강토는 공연을 앞두고 있다. 이제 무대에 올라가야 하는데, 기타가 다른 사람들의 기타와 섞이고 말았다. 또, 강토는 어떤 기타가 자기 것인지 까먹었다.
다행히도, 모든 기타는 유니크한 시리얼 넘버를 가지고 있으며, 각 시리얼 넘버는 1보다 크거나 같고, 100,000보다 작거나 같은 정수이다. 강토는 자신이 가지고 있는 기타의 시리얼 넘버를 모두 다 합하면 M의 배수가 된다는 것을 알 수 있다.
모든 기타의 시리얼 넘버와 M이 주어졌을 때, 가능한 강토의 기타 개수 중 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.
- 기타의 개수 N과 M이 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 100,000)
- 기타의 시리얼 넘버 S1 ... SN이 주어진다. (0 ≤ Si ≤ 100,000)
출력
각각의 테스트 케이스마다 시리얼 넘버의 합이 M의 배수가 되는 기타의 개수 중에서 최댓값을 출력한다.
항상 답이 존재하는 경우만 입력으로 주어진다.
예제 입력 1
2 3 5 1 8 6 6 9 8 6 4 1 2 3
예제 출력 1
3 5
힌트
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2010 Preliminaries C번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호