AMC 10 · 2018 · #2

학년 6 arithmetic

유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search

optimizationratio-proportiongreedy-algorithmextremal-constructionsystematic-enumeration extreme-principledimensional-analysissystematic-enumeration ↑ 선수 지식: ratio-proportionoptimization

📏 짧은 풀이 💡 2 개 인사이트

문제

동굴에 사실상 무한히 많은 세 가지 크기의 돌이 있습니다. 5파운드 돌은 하나에 14달러, 4파운드 돌은 11달러, 1파운드 돌은 2달러의 값어치가 있습니다. 칼은 최대 18파운드까지만 들고 나올 수 있습니다. 들고 나올 수 있는 가장 큰 총 값어치를 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 극단의 원리

무게 제한 아래에서 최댓값을 묻는 문제이므로 도구 #14(극단의 원리)가 전체를 이끈다. 한계까지 밀어붙이고, 그 너머는 불가능함을 보이는 방식이다. 부족한 자원이 파운드이므로 도구 #8(단위 살펴보기)로 돌을 '파운드당 달러'로 비교해 출발점을 잡는다. 여기서 상한이 바로 나오고, 도구 #3(가능성 지우기)이 그 상한으로 선택지 두 개를 지운다. 결정적인 한 수는 도구 #15(다르게 정리하기)이다. 세 가격을 3w-1이라는 하나의 규칙으로 다시 쓰면 세 갈래 선택이 '무겁게, 적은 개수로'라는 두 가지 목표로 바뀐다. 마지막으로 도구 #2(빠짐없이 나열하기)로 네 가지 경우를 모두 확인해 논증을 완전 탐색으로 뒷받침한다.

1STEP 1

파운드당 값어치로 재기

세 돌을 파운드당 값어치로 재 봅니다.

14/5=2.8, 11/4=2.75, 2/1=2

2STEP 2

전체 값의 상한 정하기

가장 좋은 비율이 총합의 상한을 줍니다.

2.8 · 18=50.4 → 총합 ≤ 50

3STEP 3

세 가격을 한 규칙으로 쓰기

세 가격이 모두 같은 규칙으로 쓰입니다.

14=3(5)-1, 11=3(4)-1, 2=3(1)-1 → 값=3W-N

4STEP 4

무게는 최대로, 개수는 최소로

무게는 꽉 채우고 돌 개수는 줄여야 합니다.

3 · 5=15 ＜ 18 → N ≥ 4; 5+5+4+4=18 → 3(18)-4=50

5STEP 5

더 가볍게 드는 경우 배제하기

더 가벼운 짐은 절대 이길 수 없습니다.

W ≤ 15: 3W-N ≤ 3(15)-3=42; W∈{16,17}: 3W-N ≤ 3(17)-4=47

6STEP 6

모든 경우를 나열해 확인하기

모든 경우를 확인하면 50달러입니다.

a=0:48, a=1:49, a=2:50, a=3:48 → (C) 50

정답

5+5+4+4 조합은 정확히 제한인 18파운드이고 값은 14+14+11+11=50달러이므로, 50은 어림값이 아니라 실제로 달성 가능한 값이다. 또한 파운드당 최고 비율에서 나온 상한 2.8 · 18=50.4 바로 아래에 있고, 이 상한은 51과 52를 지울 만큼 촘촘하다. 모든 경우를 나열한 목록에서도 최댓값이 50이며, 두 번째로 큰 값 49가 딱 1달러 뒤인 것은 돌을 하나 더 쓰는 조합에 대해 3W-N 규칙이 예측하는 그대로이다.

💡핵심 정리

여기 있는 돌은 모두 무게의 3배에서 1달러를 뺀 값이므로, 가장 적은 개수의 돌로 가방을 제한까지 꽉 채우면 된다.

파운드당 값어치로 재기
전체 값의 상한 정하기
세 가격을 한 규칙으로 쓰기
무게는 최대로, 개수는 최소로
더 가볍게 드는 경우 배제하기
모든 경우를 나열해 확인하기