[BOJ 1436] 영화감독 숌 - [브루트포스 알고리즘]

[BOJ 1436] 영화감독 숌 - [브루트포스 알고리즘]

문제 링크

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

문제 요약

숫자 내에 '666'이 연속으로 들어가는 수를 "종말의 수"라고 할 때, $N$번째로 작은 종말의 수를 구하는 프로그램을 작성하시오. ($N \leq 10,000$)

접근 방법

• 자료구조: 사용되지 않음 (기본 정수형 및 문자열 처리)
• 알고리즘: 브루트포스 (완전 탐색)
• 핵심 아이디어: - 첫 번째 종말의 수인 666부터 1씩 증가시키며 모든 숫자를 확인합니다.
  • 해당 숫자를 문자열로 변환한 뒤, "666"이라는 부분 문자열이 포함되어 있는지 검사합니다.
  • $N$번째 종말의 수를 찾을 때까지 이 과정을 반복합니다.

풀이 코드

#include <iostream>
#include <string>

using namespace std;

int main() {
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int num = 666; // 가장 작은 종말의 수부터 시작
    int count = 0; // 발견한 종말의 수의 개수 카운트

    while (true) {
        // 숫자를 문자열로 변환하여 "666"이 포함되어 있는지 확인
        if (to_string(num).find("666") != string::npos) {
            count++;
        }

        // N번째 종말의 수를 찾았다면 해당 숫자 출력 후 종료
        if (count == N) {
            cout << num << "\n";
            break;
        }

        num++; // 다음 숫자로 이동
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(M \cdot K)$
  • $M$은 $N$번째 종말의 수의 크기 (대략 2,666,799), $K$는 숫자의 자릿수입니다. 약 260만 번의 연산은 2초 이내에 충분히 수행 가능합니다.
• 공간 복잡도: $O(K)$
  • 숫자를 문자열로 변환할 때 자릿수만큼의 메모리를 사용합니다. (매우 미미함)

실행 결과

• 메모리: 2024 KB
• 시간: 32 ms (※ 백준 채점 환경에 따라 차이가 있을 수 있으나, 매우 안정적인 범위 내에 있습니다.)

핵심 포인트

1. 완전 탐색의 타당성: $N$이 최대 10,000으로 제한되어 있어, 숫자를 1씩 늘려가며 찾아도 시간 초과가 나지 않는다는 것을 인지하는 것이 중요합니다.
2. 문자열 변환 활용: 숫자 연산(나머지, 나누기)으로 '666' 포함 여부를 판단할 수도 있지만, to_string과 find 함수를 사용하면 코드가 훨씬 간결해집니다.

예제 확인

• 예제 1: $N=2$ 입력 시 -> 666(1번), 1666(2번) 이므로 1666 출력.
• 예제 4: $N=187$ 입력 시 -> 187번째 종말의 수인 66666 출력.
• 예제 5: $N=500$ 입력 시 -> 166699 출력.