[백준 - 1436번] 영화감독 숌 - JAVA 정리 및 해설

안녕하세요. 영화감독 숌에 대해서 정리와 해설을 해보겠습니다.

사실 처음에 볼때는 일정한 규칙을 만들어서 생각해보는 문제라고 생각했으나, 그냥 일일히 컴퓨터에 돌려도 되는 브루트포스(brutal force)문제입니다. 

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

처음에 접근할때는 이문제를 그저 규칙찾아서 규칙만들고, 문제를 풀면 된다고 생각했는데... 틀리고난 다음에 이것이 브루트포스라는 것을 확인했습니다. 

일단 규칙만드는게 안되는게 일단 규칙이 상당히 까다롭고 상황마다 경우가 달라질 수 도 있기때문에 규칙을 세워서 하는 방식은 빠르게 접었습니다.

그러면 브루트포스 방식은  직접 666이 들어가는 수를 찾아서 해결하는 것입니다. 즉, 숫자를 늘려가면서 연속된 666을 찾는 방식인 것이죠.

그럼 단순하게 생각해서 int값을 직접 +1씩 올리면서 해결하면될까요? 어차피 N이 10000정도 밖에 안되는데?

안됩니다.

왜 이런 결과를 만들까요? 이게 자리수가 점점 커지다보면 int의 범위를 벗어나기때문에 문제가 생깁니다.

그러면 이것을 어떤식을 해결하면 되냐면, 자리수 개념으로 해서 배열을 만들어주면됩니다.  이 기법은 long범위까지도 넘어가는 20!이상의 팩토리얼을 구하는 경우에도 이용할 수 있습니다. 

즉, 각 자리수를 직접 올리는 방식으로 진행해서 자리수가 10이되면 다음자리의 수를 +1을 해주는 방식으로 손으로 덧셈하는 방식과 같은 방식으로 만들어주면 됩니다.

저는 혹시 모를 overflow를 대비해서 자리수를 15자리정도를 잡고 계산을 했습니다.

그래서 연속으로 666이 나오는 순간 N을 빼주면 N값의 번호를 알 수 있고,  출력했을 때는 앞자리 0을 모두 빼주고 출력하면됩니다.

기본로직은 이렇습니다. 

15자리수를 기본으로 설정해둔뒤에 모든수를 0으로 채운뒤에 기본수인 666(왜냐면 1편은 666이 나와야합니다.)를  설정해줍니다. 저 같은 경우는 14,13,12를 1자리 10자리 100자리로 설정해서 역으로 올라기는 방식을 취했습니다.

그후 입력받은값 N이 1이 될때까지 계속 1자리 즉, 배열 t[14]++를 계속 합니다. 만약에 10이 넘었다면 모든자리수를 체크해서 어떤 자리수가 10이 넘는다면 어떤 자리수의 다음 자리수를 1을 더해주고, 현재 자리수는 0으로 만들어줍니다. 

그리고 다음에는 연속 666을 찾아보고, 있다면 N을 빼줍니다. 

그래서 나온 N=1이되는 순간에 나오는 값을 앞의 0의 자리를 뺀 모든 자리를 출력해냅니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int t[] = new int[15];
		Arrays.fill(t, 0);
		t[14] = 6;
		t[13] = 6;
		t[12] = 6;
		
		while(N>1){
			t[14]++;
			for(int i=14; i>0; i--){
				if(t[i]==10){
					t[i-1]++;
					t[i]=0;
				}
			}
			for(int i=14; i>2; i--){
				if(t[i]==6&&t[i-1]==6&&t[i-2]==6){
					N--;
					break;
				}
			}
		}
		int v =0;
		while(true){
			if(t[v]!=0){
				break;
			}
			v++;
		}
		for(int i=v; i<15;i++){
			System.out.print(t[i]);
		}
	}
}