백준 1436번 영화감독 숌, 브루트포스(완전탐색)

숫자에서 666을 찾자

처음 이 문제를 접하고 30분동안 수를 직접 구해보며 규칙이 있는지 찾아보았다.

그때 첫번째부터 18번째까지 규칙이 있는걸 찾아내어 주어진 수를 18로 나누어 몫, 나누기, 배열을 이용하려 하였다. (나중에는 저 규칙이 틀린것을 알게되었다.)

이 문제는 비교적 간단한 로직으로 해결되었다.

가장 간단한 알고리즘 중 하나인 브루트포스(완전탐색) 문제이다.

브루트포스란 ?

brute: 무식한, force: 힘 -> 무식한 힘으로 해석할 수 있다.
즉 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져가는 것이다.
이 알고리즘의 가장 큰 장점 중 하나는 예외 없이 100% 확률로 정답만을 출력한다. (하지만 그만큼 속도가 느리다는 단점이 있다.)

알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

그렇다면 이 문제를 브루트포스 알고리즘으로 해결하기 위해서 위에서 언급한것 처럼 “666”이 얼마나 반복되는지를 count 해주면서 비교하면 되는 것이었다.

그 이유를 아래에서 찾아보자.

아래는 정답코드이다.

package backjoon;

import java.util.Scanner;

public class b1436 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int num = 666;
        int cnt = 1;
        while(cnt != n) { /**원하는 번째수의 종말숫자일때까지 반복*/
            num ++;
            if(String.valueOf(num).contains("666")) { /** 666을 포함하였는가 ?*/
                cnt ++; // 포함하였을 경우에만 1증가
            }
        }
        System.out.println(num);
    }
}

위 코드에서 n은 input으로 주어지는 수이며, num은 계속 증가하는 수(가장 작은 종말의 수가 666이므로 666부터 시작한다), cnt는 종말숫자에 666이 포함되면 증가하는 count 수 이다.

즉 cnt 와 n이 같다는 것은 우리가 구하고자 하는 종말의 n번째의 수가 같을 당시의 num이라는 것이다.

따라서 cnt와 n이 같을때 반복문을 탈출하고 num을 출력해주면 되는 것이다.