[백준] 1436번 파이썬 (영화감독 숌)

1. 문제와 예제

(문제 링크 : https://www.acmicpc.net/problem/1436)

1436번: 영화감독 숌

문제

예제

1666, 6662, 166669, ... 빠짐없이 체크해야 한다. N의 최댓값이 10000인데 '_ _ _ _ 666'의 경우만 생각해도 종말의 수가 10^4=10000개가 나온다. 따라서 문제에서 준 시간 제한 2초는 1부터 수를 올려가면서 종말의 수를 일일이 찾아도 충분한 시간임을 알 수 있다. 따라서 브루트포스 알고리즘을 사용하면 되겠다. (브루트 포스가 무엇인지는 3. 풀이 에서 살펴보자)

---

2. 코드

N = int(input())

num = 666 # N 최솟값이 1이므로 666부터 시작
cnt = 0

while True:
    num = str(num) # '666' 문자열이 있는지로 판단하면 쉬우므로 str로 전환
    if (num.find('666') != -1): # '666'이 있다면
        cnt += 1 # cnt로 체크
    if cnt == N:
        break
    num = int(num) + 1

print(num)

---

3. 풀이

브루트 포스 (Brute Force)

완전탐색 알고리즘으로, 가능한 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져오는 알고리즘이다. 쉽게 말해 노가다 기법이다.
당연하게 떠올릴 수 있듯이, 장점은 정확도 100%를 보장한다는 점, 단점은 시간과 자원이 많이 든다는 점이다.

 

num을 하나씩 올려가면서 '666'이 있는지 체크하고, 있다면 그 수가 cnt번째 종말의 수가 된다. 따라서 cnt가 N이 된 순간 그 num이 N번째 종말의 수이므로 while문을 빠져나온다.