문제 보기 · Level 4 · 2017 카카오코드 예선 · 정답률 12% · 푼 사람 969명 (2026-09-30 기준)1
문제
3단 고음은 *++로 적는다. *는 음높이 × 3, +는 음높이 + 1이다. 3단 고음 뒤에 3단 고음을 잇거나(*++*++), 3단 고음 도중에 새 3단 고음을 끼워 넣을 수 있다(*+*+++). 이렇게 만들 수 있는 문자열이 올바른 문자열이다. 시작 음높이는 1이다. 최종 음높이 n이 주어질 때, 음높이가 n인 서로 다른 올바른 문자열의 수를 돌려준다.
- 5 ≤ n ≤ 2³¹ − 1
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 재귀와 백트래킹: 끝에서부터 거꾸로, 마지막 글자가
+인지*인지 두 갈래로 나누며 재귀한다. 안 될 갈래를 일찍 버리는 가지치기가 핵심이다. - 재귀적 정의와 구조적 귀납법: 올바른 문자열은
*++에서 시작해 잇기와 끼워 넣기로만 만든다. 균형 괄호와 같은 꼴의 재귀적 정의다. 이렇게 만든 문자열이 1단계의 세기 규칙을 지킨다는 것은 구조적 귀납법으로 보인다. 반대 방향(규칙을 지키면 이렇게 만들 수 있다)은 길이에 대한 귀납법으로 보인다.
1단계 · 작은 예로 손으로 풀기
올바른 문자열의 규칙을 세기로 바꾸면 이렇다. 앞에서부터 읽을 때, 어느 순간에도 +의 수는 *의 수의 두 배를 넘지 않고, 끝에서는 정확히 두 배다. * 하나가 뒤에 + 두 개를 데려와야 하기 때문이다. +**+++는 첫 글자부터 +가 넘쳐서, *+++*+는 네 글자째에서 + 3개 > * 1개 × 2라서 틀렸다.
15를 끝에서부터 되돌려 본다. 마지막 글자가 +면 앞은 14, *면 앞은 15 ÷ 3 = 5다. 그런데 *가 마지막이면 그 뒤에 와야 할 + 두 개가 없으니 안 된다. 그래서 15 ← 14 ← 13 ← 12(+ 세 개가 짝을 기다림) ← 4(*가 두 개를 가져감) ← 3 ← 1(*가 두 개를 가져감)이다. 앞에서부터 읽으면 *+*+++이다.
2단계 · 가장 단순한 방법과 그 속도
앞에서부터 *와 +를 모두 붙여 보면, 음높이가 n을 넘을 때까지 문자열이 수없이 늘어난다. n이 21억이면 어림없다.
3단계 · 핵심 아이디어
- 끝에서부터: 지금 값 v와, 뒤쪽에서 짝을 기다리는
+의 수 plus를 들고 되돌아간다.- 마지막 글자를
+로: (v − 1, plus + 1)로 간다. - 마지막 글자를
*로: v가 3의 배수이고 plus ≥ 2일 때만 (v ÷ 3, plus − 2)로 간다.
- 마지막 글자를
- 끝: v = 1이면 시작점에 닿았다. 기다리는
+가 없을 때(plus = 0)만 1개로 센다. - 가지치기: 기다리는
+가 plus개면 앞으로*가 적어도 ⌈plus / 2⌉번 더 나와야 한다.*하나마다 값이 3배이니 v는 적어도 3^⌈plus/2⌉이어야 한다. 그보다 작으면 이 갈래를 버린다. 이 가지치기 덕분에 n이 21억이어도 금방 끝난다.
4단계 · 코드 흐름
- go(v, plus): v = 1이면 plus = 0일 때 1, 아니면 0.
- v < 1이거나 3^⌈plus/2⌉ > v면 0.
- go(v − 1, plus + 1)을 더하고, v가 3의 배수이고 plus ≥ 2면 go(v // 3, plus − 2)도 더한다.
- go(n, 0)을 돌려준다.
5단계 · 파이썬 코드
def solution(n):
def go(v, plus): # 끝에서부터. plus: 짝을 기다리는 + 수
if v == 1:
return 1 if plus == 0 else 0
if v < 1 or 3 ** (plus // 2 + plus % 2) > v: # * 가 들어갈 자리가 모자라다
return 0
cnt = go(v - 1, plus + 1) # 마지막 글자가 +
if v % 3 == 0 and plus >= 2: # 마지막 글자가 *
cnt += go(v // 3, plus - 2)
return cnt
return go(n, 0)
plus // 2 + plus % 2: plus를 2로 나눈 몫을 올린 값, ⌈plus / 2⌉이다.- 재귀 깊이는 문자열 길이만큼이다. 가지치기 때문에 plus가 커지지 못해, v가 21억이어도 깊이는 수십에 그친다.
*가 s개인 올바른 문자열은 음높이가 3^s 이상이라 s ≤ log₃ n이다(로그). n = 2³¹ − 1이면 s ≤ 19라 길이는 57 이하이고, 재 보니 최대 재귀 깊이도 57이었다.
6단계 · 실행 추적
n = 15에서 들른 (v, plus)
| 들른 상태 | 한 일 |
|---|---|
| (15, 0) | +로만 갈 수 있다(plus < 2) |
| (14, 1) → (13, 2) | + |
| (12, 3) | 두 갈래: +와 * |
| (11, 4) → (10, 5) | 3³ = 27 > 10이라 버림 |
| (4, 1) | 12 ÷ 3, plus 3 − 2 |
| (3, 2) | 두 갈래 |
| (2, 3) | 3² = 9 > 2라 버림 |
| (1, 0) | 성공, 1개 |
답은 1이다.
7단계 · 복잡도와 흔한 실수
정확한 상한을 식으로 구하기는 어렵다. n = 2³¹ − 1에서 재 보니 0.2초 안팎이었다.
- 앞에서부터 만들어 가짓수가 폭발한다.
- 가지치기 없이 되돌려 n이 클 때 시간 초과가 난다.
*를 마지막 글자로 쓸 때 plus ≥ 2 조건을 빼먹어, 짝이 없는*를 허용한다.- 끝에서 plus = 0인지 확인하지 않는다.