[백준/파이썬] 1436: 영화감독 숌

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

 

문제 요약 : 666이 연속으로 들어가는 수를 '종말의 수'라고 칭한다. N이 주어졌을때 N번째로 작은 종말의 수를 구하라.

 

 

예제 입력5 :

500

 

예제 출력 5:

166699

 

📌 풀이  1  - 브루투 포스 )

잠이 와서 생각이 안나는건지, 아니면 정말 하나하나 다 돌려봐야하는 건지 감이 안 잡혀서 무작정 숫자를 나열해보았다.

666 1666 2666 3666 4666 5666 6660 6661 6662 6663 6664 ... 6669
7666 ... 9666 10666 11666 ... 16660 16661 ... 16669

 

별 규칙없어보이는 숫자들, 그리고 문제에서 제시한 N의 숫자가 10,000보다 작거나 같다는 제한을 보았을 때 브루투 포스인 것 같은데 라는 생각이 들었다.

 

브루투 포스 : 문제 해결을 위해 가능한 모든 경우의 수를 무차별적으로 시도하는 알고리즘, 최적의 해를 보장하지 않고 경우에 따라 비효율적일 수 있음

 

N = int(input())
i = 1
num = 666

while True:
    if i == N :
        break
    num += 1
    if '666' in str(num) :
        i += 1

print(num)

 

 

풀긴 풀었는데 묘~한 찝찝함에 다른 분들의 풀이를 참고해보았다.

 

📌 풀이 2 )

이 코드는 숫자의 특정 부분이 666을 포함할 경우를 고려하여 빠르게 수를 찾는 방법이다.

• i%1000 == 666 : 숫자의 끝 3자리가 666인 경우
  • 666000 ~ 666999
• i%100 == 66 : 숫자의 끝 2자리가 66이고 그 다음 숫자가 6으로 만들 수 있는 경우
  • 66600 ~ 666699
• i%10 == 6 : 숫자의 끝 자리가 6이고 그 다음 두자리로 66으로 만들 수 있는 경우
  • 6660 ~ 6669

N = int(input())
i = 0

while N > 0:
    if i % 1000 == 666:
        for j in range(1000):
            N -= 1
            if N == 0:
                print(i * 1000 + j)
                break
    elif i % 100 == 66:
        for j in range(100):
            N -= 1
            if N == 0:
                print(i * 1000 + 600 + j)
                break
    elif i % 10 == 6:
        for j in range(10):
            N -= 1
            if N == 0:
                print(i * 1000 + 660 + j)
                break
    else:
        N -= 1
        if N == 0:
            print(i * 1000 + 666)
            break
    i += 1

 

확실히 시간이 단축됐다!