백준 알고리즘 - 영화감독 숌 (1436) [Python]

 문제

 

www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

 문제 상황

 

- 666이 들어가게 하여 666부터 1666으로 시작하여 n번째 숫자를 찾는다.

 

 

 

 해결 전략

 

- dp문제라고 안내를 받았는데 풀이의 대부분은 brute force였다. 문제는 범위인 10000 이내에 숫자의 범위를 알수가 없어 속도 이슈가 발생할지 아닌지 알 수가 없다.(결과적으로 10000번째 요소는 2666799으로 속도는 매우 여유가 있다.)

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
 
N = int(input())
check = 666
while True:
    if '666' in str(check):
        N -= 1
        if N == 0: break
    check += 1
print(check)

 

 

 

 해설

 

- 666을 시작으로 1씩 증가시키며 666이 들어있으면 카운트를 줄인다.

 

- 포인트는 '666으로 어떻게 숫자를 만드냐' 라는 생각에서 '1씩 증가시키며 조건에 맞는지 확인한다'로 생각을 전환하는 것이다.

 

 

 

 새로 학습한 것 & 실수 

 

- 무조건 속도이슈가 무서워 안할 것이 아니라 일단 해볼 필요가 있다. 재귀, dp 등의 생각을 하다보니 오히려 쉬운 방법을 멀리 돌아가는 경향이 있다.