![[백준] 1055 (끝이없음)](/images/boj-1055.jpeg)
[백준] 1055 (끝이없음)
Endless 프로그램은 문자열 S 안의 모든$를 입력 문자열로 치환하는 연산을 반복합니다. 반복 횟수가 최대 10⁹이고, 결과 문자열에서 특정 구간 [min, max]을 출력해야 하므로, 실제 문자열을 구성하지 않고 각 인덱스의 문자를 효율적으로 결정해야 합니다.
핵심은 S 안의 $의 개수에 따라 전략을 나누는 것입니다: $ ≥ 2: 지수적 팽창 → 재귀$ = 1: 선형 팽창 → 모듈러
① 지수적 팽창 관찰
문자열 팽창 시뮬레이터
초기 입력과 패턴 S를 설정하고, 매 라운드마다 문자열이 어떻게 팽창하는지 관찰하세요.
지수적 팽창!
$가 2개이므로, 매 라운드마다 길이가 약 2배로 증가합니다. 6회만에 이미 379자입니다.
② $ ≥ 2: 반복 횟수 상한
반복 횟수 상한의 수학적 정당성
$의 개수를 d, S에서 $가 아닌 문자 수를 f라 하면, k번 반복 후 문자열의 길이 L(k)는 다음 점화식을 따릅니다.
d ≥ 2일 때, 이 점화식은 지수적으로 증가합니다. 일반항을 풀면:
문제에서 min, max ≤ 10⁹이므로, L(k) > 10⁹ + 100이 되는 순간부터는 더 반복해도 해당 인덱스의 문자가 바뀌지 않습니다. 따라서 C를 ⌈log₂(10⁹ + 100)⌉ ≈ 30 이하로 잘라도 정답입니다.
d = 2일 때, 길이가 10⁹를 넘기 위해 필요한 최소 반복 횟수:29회
→ 10억 회 반복할 필요 없이, 최대 29회만 시뮬레이션하면 충분합니다.
from math import ceil, log2
if S.count('$') > 1:
# d ≥ 2: 길이가 지수적 증가 → 반복 횟수를 상한으로 제한
C = min(C, ceil(log2(10**9 + 100))) # ≈ 30
# 이후 재귀로 각 인덱스의 문자를 O(C × |S|)에 계산③ 재귀 문자 탐색
재귀 문자 탐색 시각화
특정 인덱스의 문자를 찾기 위해, S의 구조를 따라 재귀적으로 내려가는 과정을 추적합니다.
④ $ = 1: O(1) 풀이
$ 1개: O(1) 모듈러 풀이
S에 $가 정확히 1개이고, 항상 맨 앞에 오므로 S = $ + tail 형태입니다. 매 라운드마다 앞부분은 그대로 유지되고 뒤에 tail이 덧붙여지는 구조가 됩니다.
구조 관찰
Round 0: I
Round 1: I + tail
Round 2: I + tail + tail
Round k: I + tail × k
O(1) 인덱싱
idx < |I| → I[idx]
idx < |I| + |tail| × C → tail[(idx − |I|) % |tail|]
그 외 → '-'
def char(idx):
if idx < len(I):
return I[idx]
if idx < len(I) + (len(S) - 1) * C: # S의 첫 글자 $를 제외한 길이
return S[(idx - len(I)) % (len(S) - 1) + 1]
return '-'왜 재귀가 안 되는가?
$ = 1이면 문자열 길이가 선형으로 증가하므로, 10⁹번 반복하면 실제로 깊이 10⁹의 재귀가 필요합니다. 이는 어떤 언어에서도 스택 오버플로를 일으킵니다. 하지만 구조가 단순하므로 O(1) 모듈러 연산으로 해결됩니다.
정리
풀이 전략 요약
재귀 탐색
O(C × |S|)
C를 ~30으로 제한, 재귀로 문자 탐색
O(1) 모듈러
O(1) per query
I + tail×C 구조를 이용한 직접 계산
핵심 인사이트
$의 개수에 따라 문자열 길이의 성장률이 근본적으로 다릅니다. d ≥ 2이면 지수적 (→ 반복 횟수 제한 + 재귀), d = 1이면 선형 (→ 모듈러 직접 계산). 이 분기가 이 문제의 핵심입니다.
구현
코드 구조
from math import ceil, log2
if S.count('$') > 1:
C = min(C, ceil(log2(10**9 + 100)))
# 이제 C ≤ 30d ≥ 2일 때, 길이가 지수적으로 증가하므로 약 30회면 10⁹을 넘깁니다. 반복 횟수를 상한으로 잘라냅니다.