[백준-1436] 영화감독 숌

문제 링크: https://www.acmicpc.net/problem/1436

코드

n = int(input())
count = 0
num = 1

while count < n:
    if '666' in str(num):
        count += 1
    num += 1

print(num - 1)

풀이

'666'이란 수가 들어가는 수로만 제목을 짓는다. 이 때 N번째 영화의 제목에 들어가는 수를 찾아야 한다.
즉 '666'이 들어가는 수를 오름차순으로 정렬했을 때 N번째 위치한 수를 찾아야 한다.

1부터 모든 수를 탐색하여 '666'이 포함되었는지 판별하고, 포함되었으면 count를 하나 올린다. 이 때 count가 n과 같아지는 시점의 수를 출력하면 된다.

근거

N은 10,000보다 작거나 같은 자연수이다. 즉 10000번째 '666'이 포함된 수를 찾는데 얼만큼의 연산이 필요할지를 판단해야 한다.

'666'이 맨 앞이던, 가운데이던, 맨 끝이던 포함된 수여야 한다. '666'이 첫번째 수라면 rough하게 생각했을 때 '666'의 앞이던 뒤던 임의의 수가 4개 붙는 수가 10000번째쯤의 수가 될 것이다.
즉 해당 수는 일곱 자리의 수가 될 것이고 이는 수백만을 의미한다.
2초의 시간 제한이 걸려있으므로 python 기준 수백만번의 탐색은 충분히 가능하니 brute-force로 이 문제를 풀 수 있다.