[백준 알고리즘] Q2193 이친수

1. Java 구현

         
import java.io.*;

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());
		long[] arr = new long[90 + 1];
		arr[1] = 2;
		arr[2] = 1;
		
		for(int i = 3; i <= n; i++) {
			for(int j = i - 2; j > 0 - 1; j--) {
				arr[i] += arr[j];
			}
		}
		
		bw.write((n == 1 ? 1 : arr[n]) + "\n");
		bw.close();
	}
}

2. 코드설명

 위에 있는 그림은 각 자리에서 나타낼 수 있는 이진수의 표현이고, 초록색 셀이 요구조건에 맞는 이친수들이다.  

 이 문제를 풀 때, Integer.toBinaryString(i) 를 사용해서 풀면 쉽다고 생각했지만, 큰 오산이었다. 90자리의 이진수를 만들기 위해서는 2^90 의 수를 표현해야

 하는데 그렇게 되면 int도 long으로도 표현이 되지 않고, BigInteger를 사용해야만 했다. BigInteger를 사용하면 시간초과가 나온다.

 그래서, 규칙성이 있을거라 생각을 했다. 그림에서 5자리의 이진수를 예를 들어보자!

 11을 가지고 있는 수는 이친수가 될 수 없기 때문에 5자리의 이친수는 반드시 10으로 시작되고 뒤에 3자리만 이친수면 된다.

 5자리의 이친수의 끝 3자리를 보면, 3자리의 이친수와 ('0' + 2자리의 이친수), ('00' + 1자리의 이친수) 가 보일 것이다. 이게 규칙이다!

 뭐라 명확한 설명은 되지 않겠지만, 그림을 보면 아차 할 것 이다!

3. Pain Point

 정수의 범위를 고려하지 않아서 문제에 틀렸다. 아직까지는 규칙성을 발견하는 것이 쉽지않다.