recursive-sequencepattern-recognitionsystematic-enumerationtree-enumerationpattern-recognitioneasier-related-problem↑ 선수 지식:systematic-enumerationpattern-recognition
📏 긴 풀이💡 4 개 인사이트
문제
조(Jo)는 매일 학교에서 6 칸짜리 계단을 오릅니다. 조는 한 번에 1 칸, 2 칸, 또는 3 칸을 갈 수 있습니다. 예를 들어 3 칸, 그다음 1 칸, 그다음 2 칸을 갈 수 있습니다. 조가 계단을 오르는 서로 다른 방법은 모두 몇 가지일까요?
문제 재정리: 조는 $6$ 칸짜리 계단을 오르는데, 한 번에 $1$ 칸, $2$ 칸, 또는 $3$ 칸을 갈 수 있습니다. 걸음의 순서가 다르면 다른 방법으로 셉니다(예: $3, 1, 2$ 와 $2, 1, 3$ 은 서로 다른 방법). 조가 꼭대기에 닿는 서로 다른 방법은 모두 몇 가지일까요?
주어진 것: 올라야 할 계단 수: $6$; 한 걸음에 갈 수 있는 칸 수: $1$, $2$, $3$ 중 하나; 걸음의 순서가 다르면 다른 방법으로 카운트 (예: $1, 2$ 와 $2, 1$ 은 두 가지); 선택지: (A) $13$, (B) $18$, (C) $20$, (D) $22$, (E) $24$
구하는 것: 합이 $6$ 이 되는 $1, 2, 3$ 들의 서로 다른 순서 있는 수열의 개수
이해
문제 재정리: 조는 $6$ 칸짜리 계단을 오르는데, 한 번에 $1$ 칸, $2$ 칸, 또는 $3$ 칸을 갈 수 있습니다. 걸음의 순서가 다르면 다른 방법으로 셉니다(예: $3, 1, 2$ 와 $2, 1, 3$ 은 서로 다른 방법). 조가 꼭대기에 닿는 서로 다른 방법은 모두 몇 가지일까요?
주어진 것: 올라야 할 계단 수: $6$; 한 걸음에 갈 수 있는 칸 수: $1$, $2$, $3$ 중 하나; 걸음의 순서가 다르면 다른 방법으로 카운트 (예: $1, 2$ 와 $2, 1$ 은 두 가지); 선택지: (A) $13$, (B) $18$, (C) $20$, (D) $22$, (E) $24$
계획
주요 도구: #7 작은 문제로 쪼개기
보조 도구: #9 더 쉬운 문제로 줄이기, #2 빠짐없이 나열하기, #5 패턴 찾기
$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$ 까지 늘려 가면 전체 수열을 한 줄도 나열하지 않고 답을 얻을 수 있습니다.
실행 — 정답: E
#9 더 쉬운 문제로 줄이기 K.OA.A.1단계 1
도구 #9 로 문제를 줄여 봅니다.
계단이 $1$ 칸뿐이면 갈 수 있는 방법은 $1$ 칸을 한 번 밟는 것 하나뿐이므로 $f(1) = 1$ 입니다.
$$f(1) = 1$$
💡 가장 작은 경우부터 직접 풀어 발판을 만드는 것이 도구 #9 의 핵심 동작입니다.
#2 빠짐없이 나열하기 1.OA.A.1단계 2
$2$ 칸짜리는 도구 #2 로 나열합니다: $(1,1)$, $(2)$ — 두 가지, 즉 $f(2) = 2$.
$3$ 칸짜리도 마찬가지로 $(1,1,1)$, $(1,2)$, $(2,1)$, $(3)$ — 네 가지, 즉 $f(3) = 4$.
$$f(2) = 2, \quad f(3) = 4$$
💡 "첫 걸음의 크기" 순서로 나열하면 빠뜨림도 중복도 없이 셀 수 있습니다.
#7 작은 문제로 쪼개기 4.OA.C.5단계 3
이제 도구 #7 을 적용합니다.
$n \ge 4$ 인 어떤 $n$ 에서든 조의 마지막 걸음을 따져 봅시다 — $1$ 이면 직전 위치는 $n-1$ 번째 칸, $2$ 이면 $n-2$, $3$ 이면 $n-3$ 번째 칸이었어야 합니다.
각각 $f(n-1)$, $f(n-2)$, $f(n-3)$ 가지를 만들어 내므로 모두 더하면 됩니다.
$$f(n) = f(n-1) + f(n-2) + f(n-3)$$
💡 "마지막 걸음이 무엇이었는가" 로 경우를 나누면 어려운 문제 하나가 쉬운 문제 셋으로 쪼개집니다 — 이것이 도구 #7 의 정수입니다.
#5 패턴 찾기 4.OA.C.5단계 4
도구 #5 로 3단계의 점화식을 활용해 패턴을 이어 갑니다.
$f(1)=1$, $f(2)=2$, $f(3)=4$ 에서 시작해 $f(4)$, $f(5)$, $f(6)$ 을 차례로 구합니다.
💡 덧셈 두 번이면 $f(6)$ 에 닿습니다 — $24$ 개의 수열을 일일이 적는 것보다 훨씬 빠릅니다.
[1]
#9 K.OA.A.1도구 #9 로 문제를 줄여 봅니다. 계단이 $1$ 칸뿐이면 갈 수 있는 방법은 $1$ 칸을 한 번 밟는 것 하나뿐이므로 $f(1) = 1$ 입니
[2]
#2 1.OA.A.1$2$ 칸짜리는 도구 #2 로 나열합니다: $(1,1)$, $(2)$ — 두 가지, 즉 $f(2) = 2$. $3$ 칸짜리도 마찬가지로 $(1,
[3]
#7 4.OA.C.5이제 도구 #7 을 적용합니다. $n \ge 4$ 인 어떤 $n$ 에서든 조의 마지막 걸음을 따져 봅시다 — $1$ 이면 직전 위치는 $n-1$
[4]
#5 4.OA.C.5도구 #5 로 3단계의 점화식을 활용해 패턴을 이어 갑니다. $f(1)=1$, $f(2)=2$, $f(3)=4$ 에서 시작해 $f(4)$, $f
[5]
#5 4.OA.C.5같은 점화식을 한 번 더 굴려서 $f(6)$ 까지 도달합니다.
검토
합리성 확인: 답 $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$ 도 일관됩니다.
대안 접근: 도구 #2(빠짐없이 나열하기)를 "부분합" 관점으로도 풀 수 있습니다. 합이 $6$ 이 되는 $1, 2, 3$ 의 다중집합은 $\{1,1,1,1,1,1\}$, $\{1,1,1,1,2\}$, $\{1,1,2,2\}$, $\{2,2,2\}$, $\{1,1,1,3\}$, $\{1,2,3\}$, $\{3,3\}$ 일곱 가지입니다. 각각의 순서 배열 수는 차례로 $1, 5, 6, 1, 4, 6, 1$ 이므로 합은 $1+5+6+1+4+6+1 = 24$ — 같은 답이 나옵니다.
사용된 CCSS 표준 (최저 학년 4)
K.OA.A.1 사물·그림 등을 사용해 덧셈과 뺄셈 표현하기 ($1$ 칸 계단을 오르는 방법이 단 하나임을 확인해 기본값 $f(1) = 1$ 을 정함.)
1.OA.A.1 $20$ 이내의 덧셈·뺄셈으로 문장제 해결 ($f(2) = 2$, $f(3) = 4$ 의 작은 경우를 모든 경우 나열로 직접 셈.)
4.OA.C.5 수의 패턴을 만들고 분석하기 (점화식 $f(n) = f(n-1) + f(n-2) + f(n-3)$ 을 세우고 한 항씩 늘려 $f(4) = 7$, $f(5) = 13$, $f(6) = 24$ 까지 계산.)
⭐ 이 AMC 8 문제는 사실 4학년 때 배운 패턴 만들기 — 마지막 한 걸음으로 경우를 나누고 작은 답들을 더하는 — 만으로도 풀 수 있어요!
⭐ 이 AMC 8 문제는 사실 4학년 때 배운 패턴 만들기 — 마지막 한 걸음으로 경우를 나누고 작은 답들을 더하는 — 만으로도 풀 수 있어요!
