[백준/Python] 1436번 영화감독 숌 문제

■ 1436번 영화감독 숌 문제

 

출처: 백준 1436번 영화감독 숌 문제

 

■ 코드 풀이

 

이번 문제도 역시나 어려웠습니다. 우선 정답 코드입니다. 이 코드는 다른 사람이 푼 코드를 참고했습니다. 먼저 666부터 시작합니다. 그리고 666에서부터 1씩 숫자를 증가시키면서 '666'이 포함되어 있다면 입력받은 N에서 1씩 빼줍니다. 최종적으로 N이 0이 되었을 때 start num에는 N번째 영화 제목이 기록되어 있게 됩니다.

 

N = int(input())

start_num = 666

while N != 0:
    if '666' in str(start_num): 
        N = N-1
        if N == 0:
            break
    start_num = start_num + 1

print(start_num)

 

아래는 제가 풀었던 코드입니다. 굉장히 복잡하게 풀었는데요. 저는 1씩 증가시키면서 모든 경우의 수를 찾기보다는, 일정 경우의 수만큼 영화 제목을 미리 생성해두려고 했습니다. 결론부터 말씀드리자면 아래 코드는 95%에서 오답으로 나옵니다. 0부터 10,000까지 100개 정도의 숫자를 대입해 보며 반례를 찾아보려고 했지만 찾지 못했습니다. 여러분들께서는 반례가 보이시나요?

나중에 시간이 나면 다시 도전해 봐야겠습니다.

 

from itertools import permutations, product

N = int(input())
order = 1
digit_num = 4
movie_names = []
find = False

# 4자리수
if N <= 19:
    arr = list('123456789')
    arr.append('666')
    permute = permutations(arr,2)
    for i,j in permute:
        if (i != '666' and j != '666'):
            continue
        movie_names.append(i+j)
    movie_names = list(map(int, movie_names))
    movie_names.sort()
    
    if N == 1:
        print(666)
    else:
        print(movie_names[N-2])
    
# 5자리수 이상
else:
    while True:
        digit_num += 1
        arr = list('1234567890')
        arr.append('666')

        prod_pairs = list(product(arr, repeat = digit_num-2))
        for prod_pair in prod_pairs:
            if ('666' in prod_pair) & (prod_pair.count('666') == 1) & (prod_pair[0] != '0'):
                temp = ''
              #  print(prod_pair)
                for prod_value in prod_pair:
                    temp += prod_value
              #  print(temp)
                movie_names.append(temp)
            else:
                continue

        movie_names = list(set(list(map(int, movie_names))))
        movie_names.sort()
        
        if (len(movie_names) + 19) >= N:
            break

    print(movie_names[N-20])