[백준] JAVA 자바 : 영화감독 숌 (1436번)

---

문제는 대강 이렇다.
따로 쓰기 귀찮으니 스샷을 참조해주십쇼.

 

사실 나는 문제를 이해하는 데만 한 10분은 걸린 것 같다...
끝내 종말을 나타내는 수는 666이 포함되는 수라고 이해할 수 있었다!

 

그러면... 우리는 아래 사항들을 고려해 보아야 한다.

1. 숫자의 끝 부분에 6이 들어가지 않는 경우

이 경우에는 그냥 현재 수의 마지막에 666을 붙여주기만 하면 된다.

 

2. 숫자의 끝 부분에 6이 하나 들어가는 경우

이 경우에는 현재 수의 마지막에 660~669까지 붙일 수 있다.
왜냐? 현재 수가 16이라면 16과 66x를 붙여서 1666x가 되어 종말을 나타내는 수가 되니까!

 

3. 숫자의 끝 부분에 6이 두 개 들어가는 경우

이 경우에는 현재 수의 마지막에 600~699까지 붙일 수 있다.

 

4. 숫자에 666이 포함되는 경우 (끝 부분이 아니어도 됨)

이 경우에는 현재 수의 마지막에 000~999까지 붙일 수 있다.

 

코드로 구현하면 아래와 같다.

 

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

public class DirectorShom {
    public static int stoi (String str) {
      return Integer.parseInt(str);
    }
  
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      int[] array = new int[10001];
      array[0] = 666;
      
      int lastCount = 0; // 마지막 수
      for (int i=0; i<10001; i++) {
        if (Integer.toString(lastCount).contains("666")) { // 666이 포함되어 있다면
          // 000~999까지 모든 수가 그 아래로 들어갈 수 있다.
          for (int j=0; j<1000; j++) {
            if (i+j < 10001) {
              array[i+j] = lastCount*1000 + j;
            }
          }
          i+=999;
        } else if (lastCount%100 == 66) { // 66으로 끝난다면
          // 600~699까지의 수가 그 아래로 들어갈 수 있다.
          for (int j=0; j<100; j++) {
            if (i+j < 10001) {
              array[i+j] = lastCount*1000 + 600 + j;
            }
          }
          i+=99;
        } else if (lastCount%10 == 6) { // 6으로 끝끝난다면
          // 660~669까지의 수가 그 아래로 들어갈 수 있다.
          for (int j=0; j<10; j++) {
            if (i+j < 10001) {
              array[i+j] = lastCount*1000 + 660 + j;
            }
          }
          i+=9;
        } else { // 6이 끝에 포함되지 않으면
          array[i] = lastCount*1000 + 666; // 맨 뒤에 666을 붙인다
        }
        lastCount++;
      }
      
      int N = stoi(br.readLine());
      System.out.println(array[N-1]);
  }
}

 

사실 이거 해결하는 데 1시간 정도 걸렸다...ㅋㅋㅋ
브루트포스는 왜 이렇게 어렵지?? 그래도 다른 알고리즘 실버 정도는 손쉽게 풀 수 있는데...ㅠㅠㅠ

아무래도 브루트포스는 더 열심히 공부해야 할 것 같다.