쿠폰 > 문제은행



실전대비 Level6

1518 : 쿠폰

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 3 회    시도횟수: 5 회   



당신은 어느 백화점의 쿠폰 2개를 받게 되었고, 쿠폰을 친한 친구의 생일 선물을 사기위해서 사용하고자 한다.

 

당신을 N 개의 물건들에 대해 조사하여 각각의 물건을 살 경우 드는 비용, 친구가 행복해할 정도, 그리고 물건을 반드시 사야 하는지를 규정하였다. 한 물건은 최대 한개만 살 수 있다. 동일한 물건을 여러번 사는 경우는 불가능하다.

 

1번 쿠폰의 경우 사려고 하는 물건 값의 합이 V1달러 이하의 선물들을 살 수 있다. 대부분의 쿠폰처럼 잔액이 남더라도 돌려 받지 못한다. 2번 쿠폰의 경우도 값이 V2인 것 빼곤 사용법이 동일하다. 두 쿠폰을 따로 사용하는 것은 가능하다. 허나 두 쿠폰의 액수를 합쳐 한 물건을 구매하는 것은 불가능하다.

 

그리고 이 백화점에선 생일인 사람의 선물을 사주려고 할 겨우, 물건 하나는 공짜로 살 수 있으며, 반드시 사야할 경우의 물건은 반드시 구매해야 한다. 물건들의 정보가 주어지고 쿠폰들의 액수가 주어졌을 때, 구매한 행복도의 합이 최대가 되는 조합을 찾는 프로그램을 작성하라.




입력의 첫 번째 줄에는 V1, V2, N(1≤V1≤500, 1≤V2≤50, 1≤N≤300)이 입력된다. 그리고 N 개의 줄에는 선물에 대한 정보 P, H, S(1 ≤ P, H ≤ 1,000)이 입력된다. P는 물건의 가격을 뜻하고, H는 그 물건을 샀을 경우의 행복도를 뜻한다.
S=1일 경우 반드시 사야하는 물건이고, S=0일 경우 반드시 살 필요가 없는 물건이다.



반드시 사야 하는 물건들을 구매하고, 그 외의 물건을 사거나 사지 않았을 때의 행복도의 최대를 출력하라.
만약에 반드시 사야 하는 물건들을 모두 사지 못할 경우에는 -1을 출력한다. -1만 출력하는 경우는 0점으로 간주한다.


3 2 4
3 10 1
2 10 0
5 100 0
5 80 0
120


3 2 4
3 10 1
2 10 0
5 100 0
5 80 1
100






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.