2728번 - 오늘은 마가리타 한 잔? 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 268 | 93 | 64 | 34.409% |
문제
청계천 근처에 사는 사람들의 주된 주말 취미는 청계천을 산책하면서 마가리타를 마시는 것이다. 청계천은 사람들이 사는 아파트(청계천엔 아파트가 하나)에서 시작해서 규현치킨에서 끝난다. 마가리타는 이 청계천을 따라 걷는 중에 보이는 가판대에서 살 수 있다.
마가리타의 가격은 재료의 양과 품질, 그리고 가판대의 분위기에 따라서 다르다. 마침 오늘 승환이가 청계천 근처로 이사왔고, 이 취미를 한 번 따라해 보려고 한다. 오늘은 승환이가 이사온 날이기 때문에, 서로 다른 마가리타의 맛을 느껴보려고 한다.
각 가판대에서 파는 마가리타 한 잔의 가격이 주어졌을 때, 승환이가 맛을 느낄 수 있는 서로 다른 마가리타의 조합이 몇 개나 되는지 계산해보려고 한다.
승환이는 각각의 가판대에서 마가리타를 많아야 한 잔만 살 수있다. 그리고, 승환이가 쓴 돈은 자신이 가지고 있는 돈의 양을 넘을 수 없고, 남은 돈으로는 구매하지 않은 그 어떤 마가리타도 살 수 없어야 한다.
예를 들어, 승환이가 지금 25만원을 가지고 있고, 각각의 가판대에서 파는 마가리타 한 잔의 가격이 다음과 같다고 하자.
- A: 8만원
- B: 9만원
- C: 8만원
- D: 7만원
- H: 16만원
- J: 5만원
위의 조건을 만족하면서, 승환이가 맛을 느낄 수 있는 마가리타의 조합은 다음과 같다.
ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23), HJ(21)
따라서, 승환이가 맛을 볼 수 있는 마가리타의 조합은 총 15가지이다.
입력
첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 가판대의 개수 V(1<=V<=30)와 승환이가 가지고 있는 돈의 양 D(1<=D<=1,000)가 주어진다. 두 값은 공백으로 구분되어 있다. 둘째 줄에는 각 가판대에서 파는 마가리타 한 잔의 가격이 주어진다. 마가리타의 비용은 항상 1보다 크다.
문제에서 주어지는 돈의 양은 모두 만원 단위이다. 따라서, 승환이가 가지고 있는 돈이 10이라면, 이는 10만원이다. 또, 마가리타 한 잔의 가격이 2라면, 2만원과 같다.
출력
각 테스트 케이스에 대해, 승환이가 맛 볼 수 있는 마가리타 조합의 개수를 출력한다. 입력은 결과 값이 항상 32 bit unsigned integer로 표현될 수 있도록 주어진다.
예제 입력 1
2 6 25 8 9 8 7 16 5 30 250 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
예제 출력 1
15 16509438
출처
ICPC > Regionals > North America > Greater New York Region > 2006 Greater New York Programming Contest I번
- 문제를 번역한 사람: baekjoon
- 빠진 조건을 찾은 사람: choiking10
- 문제의 오타를 찾은 사람: ykcha9
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호