백준 1436번: 영화감독 숌

문제

문제 바로가기> 백준 1436번: 영화감독 숌

풀이

문자열로 변경하여 반복문을 돌며 '666'이 있는 경우를 체크해주는 브루트포스 방식으로 풀었다. 반복문을 많이 사용하므로 PyPy3로 제출하면 시간을 훨씬 절약할 수 있다.(메모리는 더 많이 잡아먹지만,,)

def solution():
    import sys
    input = sys.stdin.readline
    n = int(input())
    cnt, ans = 1, 666
    while cnt!=n:
        ans += 1
        for i in range(len(str(ans))-2):
            if str(ans)[i: i+3] == '666':
                cnt+=1
                break
    print(ans)
solution()

코드 개선

다음과 같이 수학적으로 접근하면 메모리와 시간 모두 아낄 수 있다.

def solution():
    import sys
    input = sys.stdin.readline
    n = int(input())
    nlist = []
    num = 0
    while len(nlist) <= 10000:
        if not num % 10 == 6:
            nlist.append(num * 1000 + 666)
        elif (num // 10) % 100 == 66:
            for k in range(1000):
                nlist.append(num * 1000 + k)
        elif (num // 10) % 10 == 6:
            for j in range(100):
                nlist.append(num * 1000 + 600 + j)
        elif num % 10 == 6:
            for i in range(10):
                nlist.append(num * 1000 + 660 + i)
        num += 1
    print(nlist[n - 1])
solution()