[BOJ] 2193 이친수 (Java)

https://www.acmicpc.net/problem/2193

2193번: 이친수

---

1. 문제 요약

이친수란, 1~N자리의 이진수 중에서 

① 0으로 시작하지 않고

② 1이 두 번 연속 나타나지 않는 수이다.

제약조건은 1<=N<=90이다.

2. 풀이

DP를 이용하는 문제이다.

처음에는 부분집합 + 비트마스킹으로 접근하였다.

N-1자리의 수가 0이면 continue, 1이 연속해서 나오면 continue 해주는 방식으로 생각했다.

하지만 이렇게 하면 N자리 고정이기 때문에, 만약 N=5일 때, 이진수 100이 아닌 00100이 되기 때문에

100은 이친수임에도 불구하고 맨 앞에 0이 있어 이친수가 아닌 걸로 판단된다.

 따라서 이 방법은 사용할 수 없다.

 

그래서 처음엔 1의 자리부터 6의 자리까지 이친수를 직접 찾아봤다.

1의 자리 : 1 => 1

2의 자리 : 1 => 10

3의 자리 : 2 => 100, 101

4의 자리 : 3 => 1000, 1001, 1010

5의 자리 : 5 => 10000, 10001, 10010, 10100, 10101

6의 자리 : 8 => 100000, 100001, 100101, 101001, 100010, 101010, 100100, 101000

이렇게 보니 어디서 많이 본 모양새다 그것은 바로 피보나치 수열

각 자리 마다 존재하는 이친수의 개수를 담아주는 pinary[N+1] 배열을 만들었다. (0 dummy)

1의 자리, 2의 자리일 경우 1을 바로 출력하게 하였고

3의 자리부터는

① pinary[1] = 1, pinary[2] = 1을 담아주고 시작하여,

② pinary[i] = pinary[i-1] + pinary[i-2] 라는 피보나치 수열 점화식을 사용하였다.

③ for문을 돌려 3~N의 자리만큼 반복하였다.

마지막으로 pinary[N]을 출력하였다.

 

이렇게만 하고 제출하니 당연히 틀렸다고 떴다.

내가 놓친 부분은 범위의 최소값, 최대값이었다.

- 1, 2를 입력하니 ArrayIndexOutOfBoundsException오류가 났다.

    => 3일 때 부터 memoization을 해줬다.

- 90을 입력하니 오버플로우되었다.

    => pinary 배열을 int -> long 타입으로 바꿔주었다.

역시 테케는 잘 나오는데 틀렸으면 범위의 최대 최소를 확인하자

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_2193_이친수{
	
	static int N;
	static long[] pinary;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		pinary = new long[N+1];
		
		if (N == 1) System.out.println(1);
		else if (N == 2) System.out.println(1);
		else if (N >= 3) {
			pinary[1] = 1;
			pinary[2] = 1;
			//dp
			for (int i = 3; i <= N; i++) {
				pinary[i] = pinary[i-1] + pinary[i-2];
			}
			System.out.println(pinary[N]);
		}
	}
	
}