[1436] 영화감독 숌

난이도: ★★☆☆☆ • solved on: 2025-12-24

---

문제 요약

• 문제 유형: 브루트포스(Brute Force), 문자열 처리(String)
• 요구사항: N번째로 "666"(연속) 이 포함된 수를 출력해야 한다.

---

사용 개념

1. 자료구조

   • 없음 (기본 변수/문자열)

2. 알고리즘/기법

   • 브루트포스 (Brute Force)
   • 문자열 포함 검사 (substring contains)

3. 핵심 키워드

   • 부분 문자열 (substring)
   • 연속성 (consecutive)

---

풀이 아이디어

숫자 증가시키며 "666" 포함 여부 검사

1. 문제 분해

• num을 증가시키면서 문자열로 변환한다.
• "666"이 포함되면 카운트(루프 진행)로 N번째를 찾는다.

2. 핵심 로직 흐름

   for i = 1..n:
       while true:
           if String.valueOf(num).contains("666"): break
           num++
       num++   // 다음 탐색 시작점으로 이동
   출력 시 num을 1 감소시켜 결과 보정

3. 예외 처리

   • n==0 처리(다만 보통 입력 조건상 n은 1 이상이므로 불필요할 수 있음)

코드

import java.util.*;
import java.lang.*;
import java.io.*;
>
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =  sc.nextInt();
        int num = 666;
        int count = 0;
        if(n==0){
            System.out.println("666");
            return;
        }
>
        for(int i=1; i<=n; i++){
            while(true){
                count = 0;
                String str = String.valueOf(num);
                if(str.contains("666")){
                    break;
                }
                num ++;
            }
            num++;
        }
        num--;
        System.out.println(num);
    }
}

---

시간·공간 복잡도

• 시간 복잡도: O(K × L)

  • K = 검사한 숫자 개수(조건 만족 숫자 사이 공백까지 포함), L = 자릿수 길이

• 공간 복잡도: O(L) (문자열 변환)

어려웠던 점

• 처음 접근을 할 때 연속된 6 3개가 아닌 그냥 6 3개 이상으로 이해해서 오류가 났었다

---

배운 점 및 팁

• "포함"이 나오면 단순 개수 세기보다 부분 문자열(substring) + 연속성(consecutive) 조건을 먼저 의심한다.
• 브루트포스도 되지만, “정답 후보만 생성”하는 방식은 탐색 공간 자체를 줄이는 개선이 된다.
  • 하지만 이 부분은 아직 어려워서 이해가 안됐다. 궁금한 분은 아래 코드를 참고하면 된다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1436
• 참고 블로그/깃허브: 없음

---

• 참고 풀이

  “666 포함 수”를 구성적으로 생성 (탐색 범위 자체를 줄임)

핵심 아이디어(연속된 6의 접미 패턴 활용)

i를 증가시키며 아래 케이스로 “666이 포함되는 수 블록”을 생성합니다.

• i의 끝이 666이면: i000 ~ i999 (1000개)
• i의 끝이 66이면: i600 ~ i699 (100개) → 경계에서 66 + 6
• i의 끝이 6이면: i660 ~ i669 (10개) → 경계에서 6 + 66
• 그 외: i666 (1개)

이렇게 생성하면 생성되는 모든 수는 항상 "666"을 포함합니다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int count = 0;

        for (int i = 0; ; i++) {
            if (i % 1000 == 666) {
                // i000 ~ i999
                for (int j = 0; j < 1000; j++) {
                    count++;
                    if (count == n) {
                        System.out.println(i * 1000 + j);
                        return;
                    }
                }
            } else if (i % 100 == 66) {
                // i600 ~ i699
                for (int j = 0; j < 100; j++) {
                    count++;
                    if (count == n) {
                        System.out.println(i * 1000 + 600 + j);
                        return;
                    }
                }
            } else if (i % 10 == 6) {
                // i660 ~ i669
                for (int j = 0; j < 10; j++) {
                    count++;
                    if (count == n) {
                        System.out.println(i * 1000 + 660 + j);
                        return;
                    }
                }
            } else {
                // i666
                count++;
                if (count == n) {
                    System.out.println(i * 1000 + 666);
                    return;
                }
            }
        }
    }
}

---

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 2231 - 분해합
  • 백준 2798 - 블랙잭

• 확장 문제 (GPT 추천) :

  • 백준 1018 - 체스판 다시 칠하기
  • HackerRank - Closest Numbers