AMC 10 · 2002 · #9

학년 5 arithmetic
유형 Grid Tiling / Packing with Divisibility └ 세부 유형 Rectangular Tiling — Minimize Filler Count
optimizationdecimal-arithmetic greedy-algorithm ↑ 선수 지식: optimization
📏 중간 풀이 💡 2 개 인사이트
📘 쉬운 버전 보기 →
문제
각각 1.44 MB를 담는 디스크에 파일 30개를 저장해야 한다. 3개는 0.8 MB, 12개는 0.7 MB, 나머지는 0.4 MB이다. 한 파일을 두 디스크에 나누어 저장할 수는 없다. 30개 파일을 모두 담는 데 필요한 디스크의 최소 개수를 구하여라.

답을 골라 클릭하세요.

(A)
12
(B)
13
(C)
14
(D)
15
(E)
16
풀이 과정
전략 극단의 원리

디스크 개수를 최소로 하고 싶으므로, 도구 #14(극단의 원리)는 각 디스크에 담을 수 있는 만큼 최대로 담고 1.44 MB 경계를 확인하라고 한다: 어떤 파일끼리는 한 디스크에 함께 넣을 수 있고 어떤 파일끼리는 안 되는지를 따진다. 파일 크기가 세 종류이므로 도구 #7(작은 문제로 쪼개기)로 일을 세 무리로 나눈다. 가장 큰 파일부터 시작하는데, 짝지어 넣기가 가장 어렵기 때문이다. 큰 파일이 어쩔 수 없이 어떻게 놓이는지 보고, 그다음 중간 파일, 마지막으로 작은 파일을 넣으며 남는 공간을 채운다. 각 무리가 강제하는 디스크 수를 세면 실행 가능한 계획과 더 적게는 불가능하다는 증명을 동시에 얻는다.

1STEP 1

크기별 파일 수 세기

30에서 지정된 무리를 빼면 30-3-12 = 15개가 0.4 MB 파일이다.

30-3-12=15 ( 0.4 MB 파일 개수)
2STEP 2

큰 파일은 각자 디스크가 필요하다

큰 것 둘이나 큰 것과 중간은 1.44를 넘으므로, 큰 파일은 각자 디스크에 작은 것 하나씩: 3개.

0.8+0.8=1.6 ＞ 1.44, 0.8+0.7=1.5 ＞ 1.44, 0.8+0.4=1.2 ≤ 1.44
3STEP 3

중간 파일을 둘씩 짝짓기

중간 파일은 한 디스크에 둘씩만 들어가므로(0.7+0.7 = 1.4) 12개는 6개가 필요하다.

0.7+0.7=1.4 ≤ 1.44, 0.7+0.7+0.7=2.1 ＞ 1.44, 12 ÷ 2=6
4STEP 4

남은 작은 파일 묶기

작은 파일 12개가 남고 한 디스크에 셋씩(1.2 MB) 담으면 4개가 필요하다.

3 × 0.4=1.2 ≤ 1.44, 4 × 0.4=1.6 ＞ 1.44, 12 ÷ 3=4
5STEP 5

디스크 수 더하기

모든 무리가 강제되었으므로 합은 3+6+4 = 13, 보기 (B).

3+6+4=13 → (B)
정답
13
총 크기를 확인하자: 3(0.8)+12(0.7)+15(0.4)=2.4+8.4+6.0=16.8 MB이다. 1.44로 나누면 약 11.7이므로 부피만 따져도 최소 12개가 필요하고, 디스크 12개는 12 × 1.44=17.28 MB를 담아 부피로는 넉넉하다. 바로 이 점이 (A) 12가 함정인 이유다: 쪼갤 수 없다는 규칙이 공간을 낭비하게 만들어(중간 파일 디스크마다 0.04 MB씩 남는다) 13번째 디스크를 강제한다. 우리의 배치도 규칙에 맞는지 다시 보면: 1.2 MB 디스크 3개, 1.4 MB 디스크 6개, 1.2 MB 디스크 4개로 모두 1.44 이하이고, 파일은 큰 것 3개, 중간 12개, 작은 것 12+3=15개 해서 30개를 모두 담는다. 그리고 13이 진짜 최솟값이다: 큰 파일이 디스크 3개를, 중간 파일이 작은 파일을 받을 수 없는 디스크 6개를 강제하므로, 남은 작은 파일 12개는 어떻게 하든 ⌈ 12/3⌉=4개가 더 필요하다.
💡핵심 정리

가장 크고 까다로운 파일부터 담고 각 디스크를 한도가 허락하는 만큼 빽빽이 채운 뒤, 강제된 무리들을 더하면 최소 디스크 수가 나온다.

  • 크기별 파일 수 세기
  • 큰 파일은 각자 디스크가 필요하다
  • 중간 파일을 둘씩 짝짓기
  • 남은 작은 파일 묶기
  • 디스크 수 더하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.