Baekjoon 1436번 영화감독 숌

문제

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

걸린 시간

01 : 26 : 32 실패

풀이

Python3

if __name__ == "__main__":
    # 만들 영화의 개수
    N = int(input())

    # 만든 영화의 개수
    count = 0

    # 영화의 이름
    name = 0

    # 666이 들어간 영화제목이 N개만큼 나오면 종료 
    while N != count:
        name += 1

        # 연속적으로 등장한 6의 개수
        six = 0

        # 6이 3번 연속해서 나온다면
        for i in str(name):
            if six == 3:
                break

            if i == '6':
                six += 1
            else:
                six = 0

        if six == 3:
            count += 1

    print(name)

문제의 예제만 생각하고 알고리즘을 바로 작성했더니 풀리지 않는다. 뒤늦게서야 경우의 수를 생각해보니 셀 수 없을만큼 많았다. 브루트 포스 문제가 몇가지 조건문으로 해결될 리 없다.

if str(name).find("666") != -1:
            count += 1

연속되는 3개의 6을 찾기 위해 알고리즘을 직접 작성했지만 find 함수를 이용하는것보다 비효율적이다. 그래도 제한시간 2초안에 들어 시간초과는 나지 않았다.