[백준] 1436번: 영화감독 숌

 

이번 문제는 백준 난이도 실버5인 '영화감독 숌' 문제다.

 

 

 

이 문제는 종말의 수인 '666'이 들어가는 수를 작은 순으로 나열하고

제목을 시리즈 별로 제작할 때 '종말의 세상 1', '종말의 세상 2' 이런 식이 아닌 

'666'이 들어간 수를 작은 순으로 나열한 숫자로 사용하자는 의미이며

N번째 시리즈 제목을 제작하려 할 때 N번째에 해당하는 숫자가 무엇인지 찾는 문제이다.

 

실제로 나열해보면 

1     :     666

2     :     1666

3     :     2666

4     :     3666

5     :     4666

6     :     5666

7     :     6660        →       5666다음이 6660인 이유는 666이 포함되면서 6660보다 작은 수는 없기 때문이다

                                        5667이 되는 순간 5000번대에서 666이 포함되는 수는 존재하지 않는다.

 

즉 이렇게 수를 나열하면서 우리가 사용하는 1번째 2번째 대신에 새롭게 구한 수를 사용하는 것이다.

 

이 문제의 핵심은 특별한 수학적 공식이 존재하지 않는다는 것이다.

또한 문제의 조건을 보면 입력 값은 10,000보다 커지지 않는다.

 

특별한 공식이 존재하지 않고 입력 값이 작다면 브루트포스 방식을 사용해 해결할 수 있다.

가장 단순하고 효율적으로 해결할 수 있는 방법이다.

 

우리의 목표는 입력값에 해당하는 '666'이 포함된 숫자를 찾는 것이다.

즉 모든 경우의 수를 돌면서 해당하는 경우의 수를 찾는 순간 반복을 멈추고 결과를 반환하면 된다.

 

그럼 우리는 여기서 쉽게 생각해서 다른 작업 필요없이 숫자를 1씩 증가시키면서 '666'이 포함되는 숫자를 찾아 카운팅하면 된다.

 

---

 

[Python]

 

N = int(input())

num = 666
count = 1

 

우선 종말의 숫자인 '666'을 선언해준다.

종말의 세상 1 시리즈가 종말의 세상 666이 되니 count도 1로 선언해준다 (count : 시리즈 번째를 의미)

 

while True:
    if '666' in str(num):
        if count == N:
            print(num)
            break
        count += 1
    num += 1

 

우리는 목표하는 숫자를 찾을 때까지 반복해야 하기 때문에 무한 루프로 설정해준다.

그리고 조건 값으로 '666'이 포함되는 숫자를 찾아야하니 현재 num값을 스트링 형태로 임시로 변환해 '666'이 포함되는지 검사한다.

만약 포함된다면 추가로 현재 count(번째)가 입력한 번째 N과 같은지 비교한다.

같다면 해당 숫자 num이 찾는 N번째 시리즈 숫자이므로 반복문을 탈출한다.

 

그렇지 않다면 번째 수 count를 1 증가시키고 num숫자도 1을 증가시킨다.

 

import time
N = int(input())
start = time.perf_counter()
num = 666
count = 1
repeat_count = 0
while True:
    if '666' in str(num):
        if count == N:
            print(num)
            break
        count += 1
    num += 1
    repeat_count += 1

end = time.perf_counter()

print("실행 시간:", end - start, "초")
print("실행 횟수:", repeat_count)

 

이 문제의 경우 최대 입력값이 10,000이므로 최대 입력값으로 실행할 경우

약 260만번 루프를 돌고 실행 시간은 약 0.2~3초가 소요된다.

 

컴퓨터의 1초당 연산 횟수는 약 1억번이며

이 문제의 경우 순조롭게 통과할 수 있다.