AMC 10 · 2002 · #11

학년 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)

(B)

(C)

(D)

(E)

AMC 10 2002 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 각각 $1.44$ MB를 담는 디스크에 파일 $30$개를 저장해야 한다. $3$개는 $0.8$ MB, $12$개는 $0.7$ MB, 나머지는 $0.4$ MB이다. 한 파일을 두 디스크에 나누어 저장할 수는 없다. $30$개 파일을 모두 담는 데 필요한 디스크의 최소 개수를 구하여라.

주어진 것: 각 디스크는 최대 $1.44$ MB까지 담는다; $0.8$ MB짜리 파일이 $3$개; $0.7$ MB짜리 파일이 $12$개; 나머지 파일은 각각 $0.4$ MB; 한 파일을 두 디스크에 쪼개어 저장할 수 없다; 보기: (A) $12$, (B) $13$, (C) $14$, (D) $15$, (E) $16$

구하는 것: $30$개 파일을 모두 저장하는 데 필요한 디스크의 최소 개수

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #7 작은 문제로 쪼개기

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

실행 — 정답: B

#7 작은 문제로 쪼개기 4.NBT.B.4 단계 1

크기별 파일 수 세기

전체 파일은 $30$개다.
큰 파일 $3$개와 중간 파일 $12$개를 빼면 작은 파일이 몇 개 남는지 알 수 있다: $30-3-12=15$.
따라서 $0.8$ MB 파일 $3$개, $0.7$ MB 파일 $12$개, $0.4$ MB 파일 $15$개가 있다.

$$30-3-12=15 \text{ (} 0.4\text{ MB 파일 개수)}$$

💡 "나머지"란 이미 센 것을 뺀 전부를 뜻하므로, 총합에서 이름 붙은 무리를 빼면 된다.

#14 극단의 원리 5.NBT.B.7 단계 2

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

$0.8$ MB 파일을 보자.
큰 파일 두 개는 $0.8+0.8=1.6$ MB로 $1.44$보다 크므로 한 디스크에 둘을 담을 수 없다.
큰 파일과 중간 파일은 $0.8+0.7=1.5$ MB로 여전히 $1.44$보다 크므로 함께 넣을 수 없다.
큰 파일 옆에 들어갈 수 있는 것은 작은 파일뿐이다: $0.8+0.4=1.2$ MB로 $1.44$ 이하이다.
그래서 큰 파일 $3$개는 각자 디스크를 차지하고, 그 위에 작은 파일을 하나씩 얹는다.
이렇게 디스크 $3$개와 작은 파일 $3$개를 쓴다.

$$0.8+0.8=1.6>1.44,\quad 0.8+0.7=1.5>1.44,\quad 0.8+0.4=1.2\le 1.44$$

💡 가장 큰 파일이 가장 까다로우니 먼저 자리를 정하고, 옆에 들어갈 수 있는 유일한 짝을 붙여 준다.

#7 작은 문제로 쪼개기 5.NBT.A.3 단계 3

중간 파일을 둘씩 짝짓기

이제 중간 파일 $12$개다.
두 개는 $0.7+0.7=1.4$ MB로 $1.44$ 이하이므로 한 디스크에 둘이 들어간다.
세 개는 $2.1$ MB로 지나치게 많다.
중간 파일은 큰 파일의 디스크에도 낄 수 없다: 그 디스크는 이미 $0.8+0.4=1.2$ MB를 담아 $0.24$ MB만 남는데 $0.7>0.24$이기 때문이다.
그래서 중간 파일은 새 디스크에 둘씩 짝지어야 한다: $12\div 2=6$개.
이런 디스크는 각각 $1.4$ MB를 담아 $0.04$ MB만 남으므로 작은 파일도 끼워 넣을 수 없다.

$$0.7+0.7=1.4\le 1.44,\quad 0.7+0.7+0.7=2.1>1.44,\quad 12\div 2=6$$

💡 중간 파일 두 개면 디스크가 거의 꽉 차고 세 개는 절대 안 들어가므로, 둘씩 짝짓기가 가장 빽빽한 방법이다.

#7 작은 문제로 쪼개기 5.NBT.B.7 단계 4

남은 작은 파일 묶기

작은 파일 $3$개는 큰 파일 디스크에 얹었으므로 $15-3=12$개가 남는다.
세 개는 $3\times 0.4=1.2$ MB로 $1.44$ 이하이지만, 네 개는 $4\times 0.4=1.6$ MB로 지나치다.
그래서 한 디스크에 셋씩 담는다: $12\div 3=4$개.

$$3\times 0.4=1.2\le 1.44,\quad 4\times 0.4=1.6>1.44,\quad 12\div 3=4$$

💡 한도를 넘지 않는 만큼, 즉 세 개까지 작은 파일을 넣고 세 개짜리 묶음이 몇 개 필요한지 센다.

#14 극단의 원리 4.NBT.B.4 단계 5

디스크 수 더하기

각 무리가 강제한 디스크를 모두 더한다: 큰 파일 $3$개, 중간 파일 $6$개, 남은 작은 파일 $4$개.
즉 $3+6+4=13$이다.
모든 단계가 강제되었거나 디스크를 가능한 한 빽빽이 채웠으므로 더 적게 쓰는 방법은 없다.
필요한 디스크의 최소 개수는 $13$이고, 이는 보기 (B)이다.

$$3+6+4=13 \;\Rightarrow\; \textbf{(B)}$$

💡 각 무리를 최대한 빽빽이 담고 나면 무리별 합을 더한 것이 진짜 최솟값이 된다.

[1] #7 4.NBT.B.4 전체 파일은 $30$개다. 큰 파일 $3$개와 중간 파일 $12$개를 빼면 작은 파일이 몇 개 남는지 알 수 있다: $30-3-12=15$. 따

[2] #14 5.NBT.B.7 $0.8$ MB 파일을 보자. 큰 파일 두 개는 $0.8+0.8=1.6$ MB로 $1.44$보다 크므로 한 디스크에 둘을 담을 수 없다. 큰 파

[3] #7 5.NBT.A.3 이제 중간 파일 $12$개다. 두 개는 $0.7+0.7=1.4$ MB로 $1.44$ 이하이므로 한 디스크에 둘이 들어간다. 세 개는 $2.1$

[4] #7 5.NBT.B.7 작은 파일 $3$개는 큰 파일 디스크에 얹었으므로 $15-3=12$개가 남는다. 세 개는 $3\times 0.4=1.2$ MB로 $1.44$ 이

[5] #14 4.NBT.B.4 각 무리가 강제한 디스크를 모두 더한다: 큰 파일 $3$개, 중간 파일 $6$개, 남은 작은 파일 $4$개. 즉 $3+6+4=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\times 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$개는 어떻게 하든 $\lceil 12/3\rceil=4$개가 더 필요하다.

대안 접근: 무리별로 디스크를 세는 대신 낭비 공간으로 따질 수도 있다. 이 크기들로 한 디스크가 담을 수 있는 최선은 $1.4$ MB(중간 둘) 또는 $1.2$ MB(큰 하나에 작은 하나, 또는 작은 셋)이며, 어떤 조합도 $1.44$에 이르지 못한다. 그래서 모든 디스크는 적어도 $0.04$ MB를 낭비한다. 전체 내용이 $16.8$ MB이므로 완벽히 $1.44$로 채워도 $\lceil 16.8/1.44\rceil=12$개가 필요하고, 중간 및 큰 파일에서 강제되는 낭비가 요구량을 $13$으로 밀어 올린다. 두 방법 모두 (B)에 도달한다.

사용된 CCSS 표준 (최저 학년 5)

4.NBT.B.4 Fluently add and subtract multi-digit whole numbers ($30-3-12$으로 작은 파일 $15$개를 구하고 디스크 $3+6+4=13$을 더하는 데 사용.)
5.NBT.B.7 Add, subtract, multiply, and divide decimals to hundredths ($0.8+0.4=1.2$, $0.8+0.8=1.6$, $3\times 0.4=1.2$ 같은 디스크 적재량을 계산하는 데 사용.)
5.NBT.A.3 Read, write, and compare decimals to thousandths ($1.4$, $1.5$, $1.6$, $2.1$ 같은 합을 $1.44$ MB 한도와 비교하는 데 사용.)

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