[BJ] 백준 2193 이친 수 (JAVA)

문제

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

 

풀이 방법

이 문제도 dp문제다.
0과 1로만 이루어진 수를 이진수라고 하며, 다음과 같은 성질을 만족하는 수를 이친수라고 한다.
1. 0으로 시작하지 않는다.
2. 1이 연속해서 두번 나타나지 않는다.
N자리 이친수의 개수를 구하면 된다. 
2차원 dp배열을 사용해서 풀이했다. dp[N][0]에는 N자리 수이며 마지막 수가 0인 이친수의 개수, dp[N][1]에는 N자리 수이며 마지막 수가 1인 수의 개수를 저장해줬다.

그리고 이제 반복문을 돌면서 끝자리가 0인 경우에는 1과 0 모두 다 올 수 있으므로 dp[i+1][0], dp[i+1][1] 에 모두 dp[i][0]의 값을 더해줬다.
그리고 끝자리가 1인 경우에는 연속으로 1이 두번 오면 안되기 때문에 dp[i+1][0]에만 dp[i][1]을 더해줬다. 
마지막에는 dp[N][] 의 값을 다 더해서 출력한다.

 

제출 코드

import java.io.*;
public class BJ_2193_이친수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		long [][] dp = new long[N+1][2];

		dp[1][0] = 0;
		dp[1][1] = 1;

		for (int i = 1; i < N; i++) {
			dp[i+1][0] += dp[i][0];
			dp[i+1][1] += dp[i][0]; 
			dp[i+1][0] += dp[i][1];
		}
		
		long sum = 0; 
		for (int i = 0; i < 2; i++) {
			sum+=dp[N][i];
		}
		System.out.println(sum);
	}
}