pattern-recognitionsystematic-enumerationsequences-arithmeticeasier-related-problempattern-recognitionoptimization-counting↑ 선수 지식:systematic-enumerationmulti-digit-arithmetic
📏 중간 풀이💡 3 개 인사이트
문제
What is the minimum number of successive swaps of adjacent letters in the string ABCDEF that are needed to change the string to FEDCBA? (For example, 3 swaps are required to change ABC to CBA; one such sequence of swaps is ABC→BAC→BCA→CBA.)
문제 재정리: 문자열 $ABCDEF$ 에서 이웃한 두 문자를 한 번에 한 쌍씩 바꿔 가며 거꾸로 뒤집은 문자열 $FEDCBA$ 를 만들려고 합니다. 이때 필요한 인접 교환 횟수의 최솟값을 구하세요.
주어진 것: 시작 문자열: $ABCDEF$ (길이 $6$); 목표 문자열: $FEDCBA$ (뒤집은 형태); 한 번의 동작은 옆에 붙어 있는 두 문자만 자리 바꾸기; 예시: $ABC \to BAC \to BCA \to CBA$ 는 $3$ 번 교환; 선택지: (A) $6$, (B) $10$, (C) $12$, (D) $15$, (E) $24$
구하는 것: 길이 $6$ 문자열을 뒤집는 데 필요한 인접 교환의 최소 횟수
이해
문제 재정리: 문자열 $ABCDEF$ 에서 이웃한 두 문자를 한 번에 한 쌍씩 바꿔 가며 거꾸로 뒤집은 문자열 $FEDCBA$ 를 만들려고 합니다. 이때 필요한 인접 교환 횟수의 최솟값을 구하세요.
주어진 것: 시작 문자열: $ABCDEF$ (길이 $6$); 목표 문자열: $FEDCBA$ (뒤집은 형태); 한 번의 동작은 옆에 붙어 있는 두 문자만 자리 바꾸기; 예시: $ABC \to BAC \to BCA \to CBA$ 는 $3$ 번 교환; 선택지: (A) $6$, (B) $10$, (C) $12$, (D) $15$, (E) $24$
계획
주요 도구: #9 더 쉬운 문제로 줄이기
보조 도구: #5 패턴 찾기
길이 $6$ 짜리를 한 번에 셈하기는 헷갈리기 쉽습니다. 도구 #9(더 쉬운 문제로 줄이기)에 따라 길이를 줄여 봅시다. 문제가 이미 $ABC$(길이 $3$)는 $3$ 번이라고 알려 줬으니, 길이 $2$, $4$, $5$ 까지 우리가 직접 세어 보면 됩니다. 작은 경우들이 모이면 도구 #5(패턴 찾기)로 $1, 3, 6, 10, \ldots$ 의 규칙(길이가 하나 커질 때마다 다음 정수만큼 증가)을 알아내고, 그 규칙으로 길이 $6$ 의 답을 대수 없이 끌어낼 수 있습니다.
실행 — 정답: D
#9 더 쉬운 문제로 줄이기 3.OA.D.8단계 1
쉬운 경우: 길이 $2$.
$AB$ 를 $BA$ 로 뒤집으려면 한 번이면 됩니다.
기록: 길이 $2 \Rightarrow 1$ 번.
$AB \to BA$ ($1$ 번)
💡 가장 작은 경우부터 시작하면 셈에서 헤맬 일이 없습니다.
#9 더 쉬운 문제로 줄이기 3.OA.D.8단계 2
쉬운 경우: 길이 $3$.
문제에서 이미 $ABC \to BAC \to BCA \to CBA$ 가 $3$ 번이라고 알려 줬습니다.
기록: 길이 $3 \Rightarrow 3$ 번.
$ABC \to BAC \to BCA \to CBA$ ($3$ 번)
💡 문제가 준 예시를 그대로 쓰면 시간도 아끼고 셈 방식도 확정할 수 있습니다.
#9 더 쉬운 문제로 줄이기 3.OA.D.8단계 3
쉬운 경우: 길이 $4$.
마지막 문자 $D$ 를 맨 앞으로 옮기는 데 $3$ 번, 남은 $ABC$ 를 안에서 뒤집는 데 길이-$3$ 결과로 다시 $3$ 번.
💡 같은 규칙(마지막 문자를 앞으로 $5$ 번, 그 뒤에 길이-$5$ 의 $10$ 번)으로 확인해도 $5 + 10 = 15$ 로 같습니다.
[1]
#9 3.OA.D.8쉬운 경우: 길이 $2$. $AB$ 를 $BA$ 로 뒤집으려면 한 번이면 됩니다. 기록: 길이 $2 \Rightarrow 1$ 번.
[2]
#9 3.OA.D.8쉬운 경우: 길이 $3$. 문제에서 이미 $ABC \to BAC \to BCA \to CBA$ 가 $3$ 번이라고 알려 줬습니다. 기록: 길이
[3]
#9 3.OA.D.8쉬운 경우: 길이 $4$. 마지막 문자 $D$ 를 맨 앞으로 옮기는 데 $3$ 번, 남은 $ABC$ 를 안에서 뒤집는 데 길이-$3$ 결과로 다
[4]
#9 3.OA.D.8쉬운 경우: 길이 $5$. 같은 방법으로 $E$ 를 맨 앞으로 보내는 데 $4$ 번, 남은 $ABCD$ 를 뒤집는 데 $6$ 번. 합계 $4 +
[5]
#5 4.OA.C.5패턴을 봅시다. 답을 표로 늘어놓고 차이를 봅니다.
[6]
#5 4.OA.A.3패턴을 한 줄 더 늘려 길이 $6$ 까지 갑시다. 다음 증가는 $+5$, 그러므로 답은 $10 + 5 = 15$.
검토
합리성 확인: 다른 셈 방식으로도 확인해 봅시다. 처음과 끝에서 순서가 "뒤집힌" 문자 쌍이 몇 개일까요? $ABCDEF$ 에서는 모든 쌍이 알파벳 순서이고, $FEDCBA$ 에서는 모든 쌍이 반대 순서입니다. 따라서 모든 쌍이 정확히 한 번씩 엇갈려야 하고, 인접 교환 한 번은 정확히 한 쌍만 뒤집습니다. $6$ 개 문자 중 두 개를 고르는 쌍의 개수는 $\dfrac{6 \cdot 5}{2} = 15$, 그래서 최솟값도 $15$. (D) 와 일치합니다. 또한 (A) $6$ 과 (B) $10$ 은 너무 작고(길이-$5$ 만 해도 $10$), (E) $24$ 는 낭비, (C) $12$ 는 삼각수 단에 걸리지 않으므로 자연스러운 풀이가 없습니다.
대안 접근: 도구 #5(패턴 찾기)로 같은 자료를 공식으로 정리하면, 길이 $2, 3, 4, 5, 6$ 의 답 $1, 3, 6, 10, 15$ 는 삼각수 $T_{n-1} = \dfrac{(n-1)n}{2}$. $n = 6$ 을 넣으면 $T_5 = \dfrac{5 \cdot 6}{2} = 15$, 다시 (D). 위의 "쌍의 개수" 셈과 같은 발상을 식으로 적은 것뿐입니다.
사용된 CCSS 표준 (최저 학년 4)
3.OA.D.8 사칙연산을 이용한 두 단계 문장제 해결하기 (길이 $2$, $3$, $4$, $5$ 의 교환 수를 "마지막 문자를 앞으로 보내고, 나머지를 뒤집기" 두 단계로 나누어 세는 데 사용.)
4.OA.C.5 주어진 규칙을 따르는 수 패턴을 만들고 그 특징을 알아보기 (작은 경우의 답 $1, 3, 6, 10$ 을 늘어놓고 "다음 항마다 하나 더 큰 수만큼 증가" 라는 삼각수 규칙을 알아내는 데 사용.)
4.OA.A.3 사칙연산을 이용한 자연수의 여러 단계 문장제 해결하기 (패턴을 한 단계 늘려 $10 + 5 = 15$ 로 길이 $6$ 의 답을 마무리하는 데 사용.)
⭐ 문자열이 너무 길게 느껴질 땐 먼저 짧게 줄여 보자. 길이 $2, 3, 4, 5$ 는 $1, 3, 6, 10$ 번 — 다음 계단은 $+5$ 이므로 길이 $6$ 은 $15$ 번.
⭐ 문자열이 너무 길게 느껴질 땐 먼저 짧게 줄여 보자. 길이 $2, 3, 4, 5$ 는 $1, 3, 6, 10$ 번 — 다음 계단은 $+5$ 이므로 길이 $6$ 은 $15$ 번.
