1691번 - 석판 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 227 | 129 | 97 | 61.392% |
문제
고대에 유명한 조각가인 오세준은 또다른 걸작을 만들기 위한 준비 작업을 하고 있다. 그래서 가로 세로 크기가 W1×H1, W2×H2, ... Wn×Hn인 직사각형 모양의 대리석 석판이 여러 장 필요한 상태이다.
얼마 전, 세준이는 커다란 직사각형 석판을 받았다. 그래서 이것을 원하는 크기에 해당하는 석판들로 쪼개고 싶어한다. 석판은 임의의 정수 위치에서 가로나 세로로 완전히 잘라서 두 개의 직사각형 모양으로 자를 수 있다. 하지만 작은 석판들을 붙여서 큰 판으로 만들 수는 없다. 또한, 석판에는 일정한 방향으로 무늬가 있기 때문에, 회전해서 원하는 크기를 만들 수는 없다. 다시 말해, A×B라는 크기로 잘랐다면 이것을 B×A라는 크기에 맞추어 사용할 수는 없다는 뜻이다. 석판에서 원하는 크기에 해당하는 면을 모두 잘라 낸 뒤, 어느 크기로도 쪼갤 수 없어 남게 된 면들은 버려진다. 세준이는 원판을 어떻게 자르면 이러한 손실을 가능한 한 줄일 수 있을지 알고 싶어한다.
가로 길이가 21이고 세로 길이가 11인 커다란 석판을 예로 들어 보자. 그리고 우리에게 필요한 석판 크기의 종류가 10×4, 6×2, 7×5, 그리고 15×10이라고 가정하자. 이 경우 석판을 아래 그림과 같이 자르면, 각 크기에 해당하는 석판을 각각 두 장, 세 장, 세 장씩 얻으면서 손실되는 영역의 넓이는 10으로 가장 작게 된다.
15×10의 크기는 한 장이라도 넣을 경우 전체의 손실이 너무 커지기 때문에, 만들기를 포기한 것이다. 한편으로, 가장 넓이가 작은 돌판만으로 여러 장을 잘라 낸다고 해도 손실을 이보다 줄일 수 없다는 것은, 손으로 따져 보면 금방 알 수 있다.
돌판의 원래 크기와 우리가 원하는 돌판 크기들을 입력 받은 뒤, 가장 효율적으로 돌판을 자르는 방법을 계산하여 그때 손실되는 최소한의 돌판 면적의 합을 구하는 프로그램을 작성하시오. 어느 크기의 돌판을 얼마나 얻느냐가 아니라, 어떻게 자르든 손실을 줄이는 것이 목적이다.
입력
첫 줄에는 대리석 원판의 크기를 나타내는 W(가로 길이), H(세로 길이)가 들어있다. 다음 줄에는 우리가 원하는 크기의 개수 N이 있고, 그다음 N줄에는 그 크기들이 역시 가로, 세로 순으로 들어있다. 1 ≤ W, H ≤ 600이고 0 < N ≤ 200이다. 잘라야 하는 크기는 가로· 세로 모두 1 이상이고 원판의 크기 이하이다.
출력
정수 하나를 출력한다. 원판을 가장 현명하게 잘랐을 때 손실되는 면적의 최솟값이다.
예제 입력 1
21 11 4 10 4 6 2 7 5 15 10
예제 출력 1
10
출처
Olympiad > International Olympiad in Informatics > IOI 2004 > Day 2 4번
- 데이터를 추가한 사람: artichoke42
- 문제를 번역한 사람: author6
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호