2000번 - 책장제작 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 119 | 19 | 15 | 30.000% |
문제
상진이는 n개의 책을 담기 위한 책장을 만들려 한다. 그런데 상진이는 외관적인 문제 때문에 반드시 책장을 세개의 칸으로 구분하려 한다. 그런데 책장을 제작하는데는 많은 돈이 들기 때문에 책장의 크기를 최소화 하려 한다.
그런데 책장은 반드시 직사각형의 모양으로 이루어 져야 한다. 그렇다고 하였을 때, 책장의 크기는 다음과 같이 구할 수 있을 것이다. i번째 책의 높이와 두께를 각각 hi와 ti라고 하고, 첫 번째 책장에 들어가는 책의 집합을 S1, 두 번째 책장을 S2, 세 번째 책장을 S3 라고 하였을 때, 책장의 크기는 다음과 같은 식으로 구할 수 있다.
\[(\sum _{ j=1 }^{ 3 }{ max_{i\in S_{j} } h_{i} } )\times( max_{ j=1 }^{ 3 }{ \sum_{i\in S_{j} } t_{i} } )\]
이 식은 직관적으로 쉽게 알 수 있다. 각 칸의 높이는 그 칸에 들어있는 책들의 높이 중 가장 큰 높이가 될 것이고, 책장의 전체 넓이는 각 칸의 너비들 중 가장 큰 너비가 될 것이다. 그런데 각 칸의 너비는 최소한 그 칸에 들어있는 책들의 너비의 합이 되어야 하므로 위와 같은 식이 나오게 된다.
입력
첫째 줄에 책들의 개수 n이 주어진다. 그리고 두 번째 줄부터 n+1번째 줄까지 책들의 높이와 두께 hi, ti가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 책장의 최소 너비를 출력한다.
제한
- 1 ≤ n ≤ 70
- 150 ≤ hi ≤ 300
- 5 ≤ ti ≤ 30
예제 입력 1
4 220 29 195 20 200 9 180 30
예제 출력 1
18000
예제 입력 2
6 256 20 255 30 254 15 253 20 252 15 251 9
예제 출력 2
29796
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 E번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호