[PS] 백준 1436 영화감독 숌

이번에는 백준 1436번 영화감독 숌 문제를 풀어보았습니다.

이 문제는 어떤 수에 666이 연속으로 포함되어 있으면 그 수를 종말의 수라고 할 때,

N번째로 작은 종말의 수를 구하는 문제입니다.

처음에는 666의 앞뒤에 어떤 숫자가 붙을 수 있는지를 직접 만들어보는 방식으로 생각했지만,

예외가 너무 많아 오히려 복잡해졌고, 결국 수를 하나씩 증가시키면서 666이 포함되어 있는지만 확인하는 방식으로 해결했습니다.

---

문제 설명

종말의 수란 어떤 수 안에 6이 적어도 3개 이상 연속으로 들어가는 수를 말합니다.

예를 들어

• 666
• 1666
• 2666
• 6661
• 16661

같은 수들이 모두 종말의 수가 됩니다.

입력으로 N이 주어졌을 때,N번째로 작은 종말의 수를 출력하면 됩니다.

---

풀이 아이디어

처음에는 666의 앞과 뒤에 숫자가 붙는 경우를 직접 나누어 생각해보았습니다.

하지만 이렇게 접근하면

• 앞에 숫자가 없는 경우
• 뒤에 숫자가 없는 경우
• 중간에 666이 여러 번 겹치는 경우
• 0이 들어가는 경우

등 예외적인 상황이 너무 많아졌습니다.

그래서 방향을 바꾸어,

그냥 수를 1씩 증가시키면서 문자열로 바꾼 뒤 "666"이 포함되어 있는지만 검사하는 방식으로 해결했습니다.

이 문제는 N의 최대값이 10000이기 때문에,

완전탐색처럼 보여도 충분히 가능한 범위였습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    int num = 665;
    int cnt=0;

    while(true) {
        num++;
        if (to_string(num).find("666") != string::npos) {
            cnt++;
        }
        if (N == cnt) {
            cout << num;
            break;
        }
    }

    return 0;
}

---

풀이 흐름

1. 입력으로 N을 받는다.
2. num을 665부터 시작한다.
3. 반복문에서 num을 1씩 증가시킨다.
4. to_string(num)으로 문자열로 바꾼다.
5. 문자열 안에 "666"이 포함되어 있으면 cnt를 증가시킨다.
6. cnt가 N과 같아지는 순간 현재 num을 출력하고 종료한다.

---

구현 포인트

1. 666을 직접 조합하려고 하면 예외가 많아짐

처음에는 666 앞뒤에 숫자가 붙는 경우를 나누어서 만들 수 있을 것 같았습니다.

하지만 실제로는

• 숫자가 아예 안 붙는 경우
• 앞뒤에 숫자가 붙는 경우
• 6666처럼 겹치는 경우
• 여러 위치에 666이 들어가는 경우

등을 모두 고려해야 해서 구현이 훨씬 복잡해집니다.

그래서 이 문제는 오히려 규칙을 직접 만드는 것보다,

후보 수를 하나씩 확인하는 방식이 더 단순하고 안정적이었습니다.

---

2. to_string()과 find()를 이용한 검사

현재 수에 666이 포함되어 있는지는 문자열로 바꾸고 find()를 사용해서 검사했습니다.

if (to_string(num).find("666") != string::npos) {
    cnt++;
}

여기서

• to_string(num) : 숫자를 문자열로 바꿈
• find("666") : "666"이 시작되는 위치를 찾음
• string::npos가 아니면 "666"이 존재한다는 뜻

입니다.

즉, 현재 수가 종말의 수인지 한 줄로 판단할 수 있습니다.

---

3. num을 665부터 시작한 이유

첫 번째 종말의 수가 666이기 때문에,
반복문 안에서 먼저 num++을 한 뒤 검사하려면 시작값을 665로 두면 됩니다.

int num = 665;

이렇게 하면 첫 반복에서 num이 666이 되고, 바로 검사할 수 있습니다.

---

4. 완전탐색이 가능한 이유

이 문제는 얼핏 보면 비효율적으로 보일 수 있지만,

N의 최대값이 10000이라 충분히 가능한 방식입니다.

노션에도 적어둔 것처럼,

10000번째로 작은 종말의 수가 대략 큰 범위까지 가더라도 탐색 횟수가 아주 비정상적으로 크지는 않기 때문에,

수를 하나씩 늘려가며 확인하는 방식으로도 해결할 수 있습니다.

즉, 이 문제는 복잡한 규칙을 세우는 것보다

완전탐색이 가능한 범위인지 먼저 판단하는 것이 더 중요했던 문제였습니다.

---