PERKET > 문제은행

본문 바로가기


실전대비 Level2

1127 : PERKET

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 215 회    시도횟수: 482 회   



"퍼킷"은 널리 알려진 맛있는 음식이다. 퍼킷이 맛있는 음식으로 전통을 유지할 수 있던 이유는 요리사들이 "퍼킷"의 맛을 위해 재료를 고르는데 있어 신중했기 때문이다.

 

여러분에게 N개의 재료가 주어진다. S는 신맛을 B는 쓴맛을 뜻한다고 하자. 다양한 재료가 쓰인다고 할 때, 신맛의 합은 우리가 선택한 각 신맛재료의 신맛 지수들을 곱한 값이고 쓴맛의 합은 우리가 선택한 각 쓴맛재료의 쓴맛 지수들을 더한 값이다.

 

그런데 "퍼킷"은 신맛도 쓴맛도 나지 않는다. 따라서 우리는 신맛의 합과 쓴맛의 합의 차가 최소가 되도록 하고자 한다.

 

그러나 적어도 하나 이상의 재료를 선택해야한다, 그리고 물을 사용할 수 없다.


요리에 사용될 재료의 수 N(1≤N≤10)이 들어온다. 그리고 N개의 줄에는 각 재료의 S와 B가 주어진다. 모든 재료를 넣어 요리를 만들 때 신맛의 곱이나 쓴맛의 합은 모두 1,000,000,000을 넘지 않는다.



신맛의 곱과 쓴맛의 합 사이의 가능한 가장 작은 차를 출력하시오.


[Copy]
1
3 10
[Copy]
7


[Copy]
2
3 8
5 8
[Copy]
1


[Copy]
4
1 7
2 6
3 8
4 9
[Copy]
1



세 번째 예를 들어 보면 우리는 세 개의 재료를 선택할 수 있다. 신맛의 곱은 2×3×4=24이고 쓴맛의 합은 6+8+9=23이 되며 그 차는 1이다.





COCI 2008/2009 Contest#2_3_PERKET

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.