1436번: 영화감독 숌

문제

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말합니다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 입니다. N이 주어질 때, N번째로 작은 종말의 수를 구하는 문제입니다.

• 입력: 첫째 줄에 N이 주어집니다. (1 ≤ N ≤ 10,000)
• 출력: 첫째 줄에 N번째 종말의 수를 출력합니다.

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

풀이

N의 최댓값이 10,000으로 크지 않기 때문에, 가장 작은 종말의 수인 666부터 1씩 증가시키며 조건에 맞는 수를 찾는 브루트포스(완전탐색) 알고리즘을 사용합니다. N번째 수를 찾더라도 그 숫자의 크기가 약 266만 정도이므로, 시간 제한 내에 충분히 탐색할 수 있습니다.

1. 탐색 시작: 변수 i를 666부터 시작하여 무한 루프(for (int i = 666; ; i++))를 돕니다.
2. 조건 확인: 정수 i를 문자열로 변환(String.valueOf(i))한 뒤, contains("666") 메서드를 사용하여 "666"이 연속으로 포함되어 있는지 확인합니다.
3. 카운트 및 종료: "666"이 포함되어 있다면 카운트(cnt)를 1 증가시킵니다. 카운트가 목표값 N과 같아지는 순간이 곧 N번째 종말의 수를 찾은 것이므로, 해당 숫자를 출력하고 루프를 종료(break)합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());

       int cnt = 0;
       
       // 666부터 시작하여 1씩 증가시키며 완전탐색
       for (int i = 666; ; i++) {
          // 숫자를 문자열로 변환하여 "666"이 포함되어 있는지 검사
          String s = String.valueOf(i);
          if (s.contains("666")) {
             cnt++;
          }

          // N번째 종말의 수를 찾았다면 출력 후 루프 종료
          if (cnt == n) {
             bw.write(i + "");
             break;
          }
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force)