[백준] 1436 영화감독 숌 - python

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

1436번: 영화감독 숌

 

처음에 그냥 입력받은 N-1 + '666'만 붙이면 되는 줄 알고,

뭐야 이거 쉽네? 했으나

N = 187 을 보고, 쟤 왜 저러지.

잘못 이해했음을 깨달았다 !!

 

무조건 N + 666 이게 아니고 . .

6660 6661 6662 6663 6664 이런게 잔뜩 존재한다는 점,

심지어 N은 최대 만까지도 간다는 점 . .

 

내가 한 생각 :

처음엔 그냥 숫자 다돌려서 리스트를 만들고, 거기서 666이 들어간 것을 골라낼까 생각했다.

근데 입력 N이 10000이하인거지 . . 영화 번호가 10000까지 인게 아니여서

도대체 숫자 어디까지 리스트를 만들어야할지 감이 안오고

100퍼 시간초과를 예상했다.

그럼 . . 어떻게 하냐 ! 완탐 돌리면 안되겠는데 !

 

결국은 완탐으로 푼 것 같긴한데 ~

내가 생각한 먼저 숫자 다 만들어놓기 X

만들면서 찾으면 멈추기 O

N = int(input())
cnt = 0
start = 666
while True:
    # start를 문자열로 바꾼 것에 666이 있으면 cnt 증가
    if '666' in str(start):
        cnt += 1
    # N번째를 찾았으면 멈추기
    if cnt == N:
        print(start)
        break
    # N번쨰를 찾지못했으면 start 1씩 증가
    start += 1

 근데 어떻게 시간초과 안난지 아직 잘 모르겠다.

생각보다 시간이 얼마 안걸리나 ?

스터디 친구들에게 물어보고 글에 다시 써놔야겠다 !