경시 · AMC 대비 · 4단계 중 4

AMC 8 · 2010 · #25

학년 4 counting
유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count
recursive-sequencepattern-recognitionsystematic-enumeration tree-enumerationpattern-recognitioneasier-related-problem ↑ 선수 지식: systematic-enumerationpattern-recognition
📏 긴 풀이 💡 4 개 인사이트
문제
조는 6 칸짜리 계단을 오르는데, 한 번에 1 칸, 2 칸, 또는 3 칸을 갈 수 있습니다. 걸음의 순서가 다르면 다른 방법으로 셉니다(예: 3, 1, 2와 2, 1, 3은 서로 다른 방법). 조가 꼭대기에 닿는 서로 다른 방법은 모두 몇 가지일까요?

답을 골라 클릭하세요.

(A)
13
(B)
18
(C)
20
(D)
22
(E)
24

AMC 8 2010 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정
전략 작은 문제로 쪼개기

6 칸 전부를 한 번에 나열하면 실수하기 쉬우므로, 먼저 도구 #9(더 쉬운 문제로 줄이기)로 f(1), f(2), f(3)을 도구 #2(빠짐없이 나열하기)로 직접 셉니다. 그다음 도구 #7(작은 문제로 쪼개기)이 결정적인 아이디어를 줍니다 — 조의 마지막 걸음이 1, 2, 3 중 무엇이었든 그 직전 상황은 같은 종류의 더 작은 문제일 뿐이라는 점이죠. 그러면 f(n) = f(n-1) + f(n-2) + f(n-3)으로 한 문제가 세 개의 작은 문제로 쪼개지고, 도구 #5(패턴 찾기)로 이 규칙을 n = 6까지 늘려 가면 전체 수열을 한 줄도 나열하지 않고 답을 얻을 수 있습니다.

1STEP 1

계단 1개 경우 세기

먼저 문제를 줄입니다 (도구 #9): 계단이 1 칸이면 방법은 하나뿐, 즉 f(1) = 1.

f(1) = 1
2STEP 2

계단 2, 3개 경우 세기

직접 나열합니다 (도구 #2): 2 칸은 (1,1),(2)로 f(2) = 2, 3 칸은 네 가지로 f(3) = 4.

f(2) = 2, f(3) = 4
3STEP 3

점화식 세우기

마지막 걸음으로 나눕니다 (도구 #7): 직전 위치가 n-1, n-2, n-3 이므로 f(n-1) + f(n-2) + f(n-3).

f(n) = f(n-1) + f(n-2) + f(n-3)
4STEP 4

계단 4개까지 확장하기

이제 패턴을 이어 갑니다 (도구 #5): 1, 2, 4 에서 규칙을 쓰면 f(4) = 7.

f(4) = 4 + 2 + 1 = 7
5STEP 5

계단 6개까지 이어가기

점화식을 한 번 더 굴리면 f(5) = 13, 이어서 f(6) = 24 — 정답 (E).

f(5) = 7 + 4 + 2 = 13, f(6) = 13 + 7 + 4 = 24 → (E)
정답
24
답 24는 선택지 중 가장 큰 값이고, 6 칸 계단에 세 가지 걸음 크기를 자유롭게 섞을 수 있으니 경우의 수가 꽤 많을 거라는 직관과도 맞습니다. f(4) = 7을 직접 나열해 검토하면 (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3), (3,1) — 정확히 7 개입니다. 점화식이 옳으니 f(6) = 24도 일관됩니다.
💡핵심 정리

이 AMC 8 문제는 사실 4학년 때 배운 패턴 만들기 — 마지막 한 걸음으로 경우를 나누고 작은 답들을 더하는 — 만으로도 풀 수 있어요!

  • 계단 1개 경우 세기
  • 계단 2, 3개 경우 세기
  • 점화식 세우기
  • 계단 4개까지 확장하기
  • 계단 6개까지 이어가기

가족의 부모 대시보드는 sensimlab.com에 있습니다.

비슷한 유형 더 풀어보기

같은 유형의 문제예요. 태그는 이 문제와 겹치는 부분이에요.