[Python] 백준 알고리즘 #1436 영화감독 숌

문제풀이

 

이 문제에서 해결할 때 사용해야 할 알고리즘은 '브루트 포스 알고리즘'으로 해결한다.

 

'브루트 포스 알고리즘' 이란? 

완전탐색 (Brute-Force) 즉 BP라고 도 부르며, 쉽게 말해서 모든 경우의 수를 전부 따져 보는 것이다. 

 

이 알고리즘은 가장 단순하고 간단한 알고리즘이지만, 답을 무조건 찾을 수 있고 정확하다. 

 

입력 값 N은 10,000보다 작거나 같은 자연수이다. 그래서 단순히 666부터 큰 수 까지 반복한다고 생각했을 때 시간 초과가 발생하였다. 

import sys
input = sys.stdin.readline

n = int(input())
count_r = 0

for i in range(666, 10000000):
    temp = str(i)
    count = 0
    for j in range(len(temp)):
        if temp[j] == '6':
            count += 1
    if count >= 3:
        count_r += 1
    if count_r == n:
        break
print(i)

 

반복문 아래 또 반복문이 발생하여서 시간초과가 걸린 것 같아, 다음과 같이 수정해 주었지만 틀린 답이라는 결과가 나왔다. 

import sys
input = sys.stdin.readline

N = int(input())
movie = 666

while True:
    if str(movie).count('6') >= 3:
    	count+=1
    movie+=1
    if count==n:
    	break
        
print(movie-1)

 

문제를 다시 읽어보니 '종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다.'

6이 3번 들어가는 것이 아니라, 연속된 6이 3번 이상일 경우이다.

 

문제를 잘 읽어봐야겠다... 

 

따라서 

'666' 이라는 문자열이 1번 이상만 들어가는 숫자를 구하면 된다. 

 

소스코드

import sys
input = sys.stdin.readline

n = int(input())
movie = 666
count = 0
while True:
    if '666' in str(movie):
        count+=1
    movie+=1
    if count==n:
        break
print(movie-1)

 

 

www.acmicpc.net/problem/1436

1436번: 영화감독 숌