문제 이해

이진수를 만드려고 한다.
이 때 0을 활용하려면 0을 연속 2개 활용해야 한다. 1은 특정 제한이 없다.
(ex) 01은 불가, 001은 0이 연속 2번 나왔으므로 가능

2진수 총 N자리를 만드려고 할 때, 위 조건으로 총 몇개의 이진수를 만들 수 있는지 구하는 문제이다.

---

문제 풀이

1. N = 1일 때 1개
2. N = 2일 때 2개
3. N = 3일 때 3개 = (N=1 Case) + (N=2 Case)
   ...

만약 N= (k-1), (k-2)일 때 각각 $n_{k-1}$, $n_{k-2}$만큼 만들 수 있다고 가정하자.
이 때 N = (k-1)인 이진수 가장 앞쪽에 1을 붙이면 N = k인 Case가 될 것이다.
(ex) 001일 때 앞에다가 1을 붙여 1001을 만들면 N = 4인 Case를 만들 수 있음
앞쪽에 붙인 이유는, 만약 뒤에다 붙이면 0011이 될텐데 이 방법은 11 앞에 00을 붙이는 Case와 동일해진다. 따라서, 00과 1을 모두 앞에다 붙이면 절대로 동일해질 수 없다.
(왜냐하면 맨 앞 수는 00으로 시작하거나 1로 시작할 것이기 때문에 절대 겹칠 수 없음)

(k-2)인 Case에도 앞쪽에 00을 붙이면 N = k인 Case를 만들 수 있을 것이다. 따라서, $n_k$ = $n_{k-1} + n_{k-2}$가 될 것이다

즉, 피보나치 수열을 구하는 문제이며, 우리가 알고 있는 DP 방식으로 피보나치 수열 문제를 풀듯이 풀면 될 것이다.

---

코드

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


public class Main {
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		int N = sc.nextInt();
		if(N==1) {
			System.out.println(1);
			return;
		}
        // N = 1일 경우 dp[2]가 저장될 공간이 없어 에러가 발생
        
		int[] dp = new int[N+1];
	
		dp[1] = 1;
		dp[2] = 2;
		
		for(int i=3;i<N+1;i++) {
			dp[i] = (dp[i-1] + dp[i-2])%15746;
            // DP를 활용한 피보나치 수열 문제 풀기
		}
		System.out.println(dp[N]%15746);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 런타임 에러 : N = 1인 Case는 따로 처리해줬어야 했는데, 따로 처리해주지 않아 IndexOutOfBounds Error가 발생하였다.