문제 이해

0과 1로만 이루어진 N자리 수 중 아래 조건을 만족하는 수의 개수를 구하는 문제이다.

1. 0으로 시작하지 않는다.

2. 1이 두 번 연속으로 나타나지 않는다.

---

문제 풀이

N*2배열을 준비하여, arr[N][0]은 N번째 자리에 0을 준비했다는 뜻, arr[N][1]은 N번째 자리에 1을 준비했다는 뜻으로 문제를 해결하면 된다.

1이 연속으로 2번 나올 수 없으므로 arr[N-1][1]은 arr[N][0]의 값만 사용하고, arr[N][0]은 arr[N-1][0], arr[N-1][1] 모두 사용할 수 있다.

이친수는 0으로 시작하지 않으므로 arr[0][0] = 0, arr[0][1] = 1로 설정해주면 될 것이다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static long[][] DP;
	
	static void dp() {
		DP[1][0] = 0;
		DP[1][1] = 1;
		
		for(int i =2;i<N+1;i++) {
			DP[i][0] = DP[i-1][0] + DP[i-1][1]; 
            // i-1번째에 0, 1 둘 다 들어와도 됨
			DP[i][1] = DP[i-1][0];              
            // i-1번째에 0이 들어가는 경우밖에 존재하지 않음
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		DP = new long[N+1][2];
		//DP[i][0] : i번째에 0이 들어간 Case
		//DP[i][1] : i번째에 1이 들어간 Case
		
		dp();
		
		System.out.println(DP[N][0]+DP[N][1]);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 틀렸습니다 : 정답이 될 수 있는 최댓값이 int형으로 처리할 수 있는 범위를 넘어가기 때문에 long으로 처리해줘야 한다.