백준 | 영화감독 숌

백준 영화감독 숌 문제 풀이이다.

입력 n에 해당하는 영화 제목에 포함된 숫자를 출력하는 문제이다.

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 의미한다.

즉, 가장 작은 종말의 수는 666이고, 처음 만든 영화 제목은 '세상의 종말 666'이 된다.

그 다음 영화의 제목은 '세상의 종말 1666', '세상의 종말 2666'과 같은 규칙으로 만들어진다.

예를 들어, n이 7이라면 영화의 제목은 '세상의 종말 6666'이 된다.

만약 영화의 제목을 만드는 규칙이 666으로 끝나는 수라면 str(n - 1) + '666'과 같은 꼴로 쉽게 만들 수 있을 텐데, 이 문제는 그렇지 않다.

왜냐하면 666이 숫자 앞에 오거나 가운데에 포함되는 것도 종말의 수이기 때문이다. (66612, 316661 등)

그래서 간단한 문제는 아니다..

그런데 시간 제한 2초에 대해 n은 10,000 이하의 자연수이고, 666이라는 패턴은 꽤 많이 나타나기 때문에 브루트 포스(완전 탐색)로 접근해도 괜찮겠다는 생각이 들었다.

가장 작은 종말의 수인 666부터 1씩 늘려가며 n번째 종말의 수를 찾으면 된다!

코드(정답)는 다음과 같다.

import sys


# 입력
n = int(sys.stdin.readline())

# 영화 제목 숫자 찾기
cnt = 0
title_num = 666

while True:
    if '666' in str(title_num):
        cnt += 1

    if cnt == n:
        break

    title_num += 1

# 출력
print(title_num)

위의 코드 10,000을 입력해보면, 10,000번째 종말의 수가 2,666,799임을 알 수 있다.

즉, 브루트 포스로 접근해도 시간 초과가 발생하지 않는다!