[Python] 백준 1436번 - 영화감독 숌

문제 개요

분류

브루트포스 알고리즘

문제 설명

666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

풀이

초기 접근

저는 이 문제를 brute force로 직접 경우의 수를 permutation, product로 구현하려고 시도했습니다.

666이 하나로 붙어있어야 하므로 이를 문자 'a'로 치환했습니다. N이 10,000 이하이니 숫자 하나와 a, 숫자 두 개와 a, 이런 식으로 순열이 총 몇 가지 나오는지 세어보려 했습니다 (물론 구현도 엉망이었습니다) :

from itertools import permutations, product

T = int(input())

numbers = "0123456789"
devil = "a"

attempt1 = product(numbers, devil)

output = list(attempt1)

attempt2 = product(numbers, repeat=2)
attempt2 = permutations(attempt2, devil)

output2 = list(attempt2)

print(output, len(output))
print(output2, len(output2))

그러나 곧 잘못된 접근임을 깨달았습니다. 이 문제는 최대 경우의 수가 제한돼 있어 그나마 봐줄 만하지만, 제한이 없는 문제였다면 좋지 않은 방식입니다.

666을 포함하면서 왼쪽으로 숫자가 붙는 경우와 오른쪽으로 붙는 경우가 모두 가능하고, 숫자를 비교해 오름차순을 유지하며 확인해야 해서 구현이 더 까다로워집니다.

정답 풀이

이보다는 숫자를 하나씩 키워가며 그 안에 666이 붙어 있는지 확인하고, 맞으면 카운트를 올리는 방식이 적절합니다.

영화의 첫 번호는 무조건 666부터 시작하니 초기값을 666으로 두고 1씩 늘립니다. 무한 루프 안에서 '666'이 들어 있는지 검사하는 분기를 만들고, 들어 있으면 카운트 변수 count를 1 증가시킵니다.

이 count 변수가 입력으로 주어진 숫자와 같아지면 무한 루프를 탈출하고 최종적으로 저장된 숫자를 출력하면 됩니다.

T = int(input())

count = 0
devil = 666

while True:
    if '666' in str(devil):
        count += 1
    if count == T:
        break
    devil += 1

print(devil)