백준 - 1436번 영화감독 숌 python 문제풀이 [Hellfer]

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

1436번: 영화감독 숌

🔷 알고리즘 분류 - 브루트포스 알고리즘  난이도 - 실버 5 

예를 들어, 4자리의 암호를 알아내야 하는 상황에서 브루트포스 알고리즘을 사용하면 0000부터 9999까지 모든 숫자를 하나씩 대입하여 암호를 찾아냅니다. 또한, 정렬되지 않은 배열에서 특정 값을 찾는 경우, 배열의 처음부터 끝까지 모든 요소를 검사하여 원하는 값을 찾는 것도 브루트포스 방식의 예시입니다.

브루트포스 알고리즘의 장점은 그 구현이 매우 단순하며, 해가 존재한다면 반드시 그 해를 찾을 수 있다는 것입니다. 즉, 완전성을 보장한다는 점입니다.

하지만, 이 알고리즘은 가능한 모든 경우의 수를 다루기 때문에, 경우의 수가 많은 문제에서는 연산 속도가 매우 느려집니다. 즉, 시간 복잡도가 매우 높다는 단점이 있습니다. 이러한 이유로, 브루트포스 알고리즘은 문제의 규모가 작거나 최악의 경우를 고려하지 않아도 되는 상황에서 주로 사용됩니다.

🔶 문제 풀이 - 브루트포스 알고리즘을 이용한 풀이

# 사용자로부터 입력을 받아 정수로 변환하여 N에 저장합니다.
N = int(input())

# 영화 제목에 사용되는 숫자를 저장하는 변수를 666으로 초기화합니다.
movie = 666

# N이 0이 될 때까지 반복합니다.
while N:
    # 만약 현재 movie 값에 '666'이 포함되어 있다면,
    if '666' in str(movie):
        # N을 1 감소시킵니다.
        N -= 1
    # movie 값을 1 증가시킵니다.
    movie += 1

# N번째 영화 제목에 사용된 숫자를 출력합니다.
# while문을 빠져나올 때 movie 값이 하나 더 증가되어 있으므로, 1을 빼서 출력합니다.
print(movie - 1)

🔶 초보자를 위한 코드풀이

# N이 0이 될 때까지 반복합니다.
while N:
    # 만약 현재 movie 값에 '666'이 포함되어 있다면,
    if '666' in str(movie):
        # N을 1 감소시킵니다.
        N -= 1
    # movie 값을 1 증가시킵니다.
    movie += 1

 

 

우선 N을 3이라고 가정해 봅시다. 즉, 666이 포함된 숫자 중에서 세 번째 숫자를 찾는 문제가 됩니다.

처음에 movie 변수는 666으로 설정되어 있습니다. 이후 while문이 시작되는데, 이는 N이 0이 아닐 때까지 반복되는 루프입니다.

1. 첫 번째 루프에서 '666'이 str(movie)에 포함되어 있으므로 N을 1 감소시킵니다. 이제 N은 2입니다. 그리고 movie 값을 1 증가시키므로 movie는 이제 667입니다.

2. 두 번째 루프에서 str(movie)는 '667'이므로 '666'이 포함되어 있지 않습니다. 따라서 N은 그대로 2이고, movie는 1 증가하여 668이 됩니다.

3. 이런 식으로 movie를 1씩 증가시키면서 '666'이 포함되는 숫자를 찾습니다. 이때 N은 '666'이 포함될 때마다 1씩 감소합니다.

4. movie가 1666이 되면 '666'이 포함되므로 N을 다시 1 감소시키고, 이제 N은 1입니다.

5. movie가 2666이 되면 '666'이 포함되므로 N을 다시 1 감소시키고, 이제 N은 0입니다.

이제 N이 0이 되었으므로 while문을 빠져나오고, movie - 1을 출력합니다. movie는 while문을 빠져나올 때 1 증가된 상태이므로, 원하는 숫자를 얻기 위해선 1을 빼줘야 합니다. 

따라서 출력 결과는 2666이 됩니다. 이는 666이 포함된 숫자 중에서 세 번째 숫자입니다.

 

🤗파이팅입니다~ 여러분!!🤗