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

문제 개요

https://www.acmicpc.net/problem/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)