문제 1024 · 기초 4
점심 메뉴 조합
완전 탐색 · 비트마스크
테스트별 제한 2000ms · 브라우저 채점
문제
회사 앞 분식집 메뉴판에 메뉴 N개가 있다. i번째 메뉴의 가격은 p_i 원이고, 팀원들이 매긴 만족도는 s_i 점이다. 점심 예산 B원 안에서 메뉴를 골라 만족도 합이 가장 크게 하려 한다. 같은 메뉴는 한 번만 시킬 수 있고, 아무것도 시키지 않아도 된다. 만족도 합이 가장 큰 조합이 여럿이면 그중 가격 합이 가장 작은 조합을 고른다. 그때의 만족도 합과 가격 합을 구하라.
입력
첫째 줄에 N 과 B 가 주어진다. (1 ≤ N ≤ 15, 0 ≤ B ≤ 300,000) 다음 N개 줄에 p_i 와 s_i 가 주어진다. (100 ≤ p_i ≤ 30,000, 1 ≤ s_i ≤ 100)
출력
만족도 합과 가격 합을 공백으로 구분해 출력한다.
예제 입력 1
4 10000 4500 30 6000 45 3000 20 2500 15
예제 출력 1
65 9000
예제 입력 2
2 1000 1500 10 2000 20
예제 출력 2
0 0
힌트 펼치기
- 메뉴가 15개 이하이므로 고르는 방법은 2^15 = 32,768가지뿐이다. 전부 확인해도 된다.
- 0 부터 2^N − 1 까지의 정수 mask 에서 i번째 비트가 1 이면 i번째 메뉴를 고른 것으로 보자.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.