[실버5]백준 1436번(영화감독 숌) - 코테공부 41일차(2025.03.10)

문제유형

브루트 포스 알고리즘

풀이 방법 도출 과정

1. 영화 제목을 짓는데 순서가 666, 1666, 2666이렇게 짓는 다는 것이다. 6이 적어도 3이상 연속으로 들어가는 수를 찾는 다는 것이다.

2. 일반화해서 생각하면 N번째 영화의 제목은 세상의 종말(N번째로 작은 종말의 수)와 같다. 

3. 처음에는 단순히 (N-1) 뒤에 666을 붙이면 영화 제목이 나온다고 생각할 수 있다. 예로 들어 500번째 영화 제목은 499666이라고 예상할 수 있다.

4. 하지만 실제로는 모든 종말의 수를 작은 수부터 정렬했을 때 500번째는 166699가 된다. 이는 단순히 (N-1)666형태가 아니다. '666'을 포함하는 모든 수를 오름차순으로 나열했을 떄의 순서이기 때문이다.

5. 예로 들어서 순서는 다음과 같다. 666, 1666, 2666, 3666, 4666, 5666, 6666, 6660이렇게 된다.  

 

5. 따라서 정확한 N번째 종말의 수를 구하기 위해서는 666이 포함된 수를 차례대로 찾는 알고리즘을 구현해야한다. 666이 포함된 수를 하나씩 검사하며 카운트하여, N번째에 해당하는 값을 찾는 알고리즘을 만들어보도록 하겠다. 

시간 복잡도

시간 복잡도는 여러가지 num에 영향을 많이 받지만 num도 N에 의해서 움직이기 때문에 대략적으로 O(N)이다. 시간복잡도가 최악이 될 경우 1만이기에 시간복잡도 부분에서 안정하다. 

코드 및 간단설명

브루트 포스 알고리즘을 사용하여 풀었다. 

N = int(input())

count = 0
num = 666

while True:
    if '666' in str(num):
        count += 1
        if N == count:
            print(num)
            break
    num += 1

다른 풀이

1)  브루트 포스보다 666을 더 빠르게 찾는 방법

브루트포스 방식보다 더 빠르게 '666'을 포함하는 숫자를 찾는 방법은 다음과 같다. 먼저, '666'이 포함된 숫자를 앞에서부터 생성하면서 탐색을 진행한다. 또한, '6666'이 포함된 경우를 활용하여 이후 숫자를 한 번에 처리함으로써, 불필요한 탐색을 줄이고 시간 복잡도를 크게 감소시킨다. 더 나아가, 가능한 숫자 범위를 미리 계산하여 여러 개의 숫자를 한꺼번에 건너뛰면서 목표한 N번째 숫자를 빠르게 찾는다. 이러한 최적화 기법을 통해 연산량을 크게 줄이고, 보다 효율적으로 '666'이 포함된 수를 찾을 수 있다.

N = int(input())
cnt = 0
leading_digit = 0
num = "666"

while True:
    cnt += 1
    num = str(leading_digit) + "666"
    idx = num.find("6666")
    
    if idx >= 0:
        idx += 3
        num_length = len(num)
        remaining_length = num_length - idx
        max_increment = 10 ** remaining_length - 1
        
        if max_increment + cnt >= N:
            num = num[:idx] + str(N - cnt).rjust(remaining_length, "0")
            break
        else:
            cnt += max_increment
    
    if cnt == N:
        break
    
    leading_digit += 1

print(int(num))