BOJ 1436 - 영화감독 숌

문제

https://www.acmicpc.net/problem/1436

 

 

풀이

완전탐색을 이용해 문제를 해결한다

 

규칙을 파악하면 다음과 같다

666, 1666, 2666, 3666, 4666, 5666, 6660, 6661, 6662, 6663, 6664

규칙을 수학적인 규칙으로 접근하려면 오래걸린다

따라서 1부터 숫자를 증가시켜서 666이 포함됐는지 확인한다

 

N의 최대값이 10,000이고, 이때 666 숫자는 266799이다

 

1 ~ 2666799까지 탐색과 666찾기가 최대 O(n^2) 시간 복잡도로 해결이 가능하다

 

 

코드

python

current = 0
answer = 1
 
n = int(input())
 
while True:
    if "666" in str(answer):
        current += 1
 
    if current == n:
        break
 
    answer += 1
 
print(answer)