[Baekjoon]2193. 이친수(DP)

Baekjoon 

#2193. 이친수 

http://www.acmicpc.com/problem/2193

---

개인적으로 오르막수나 쉬운 계단 수 문제보다 훨씬 쉽다고 생각했다. 이미 앞에 두 문제를 어떻게 접근하는지 알고 있어서 그런 것일 수도 있겠지만 코드 자체도 훨씬 간단하고 이해하기도 쉬웠다. 이 문제도 마찬가지로 배열d를 정의한다.

d[N][k] : N자리 k로 끝나는 이친수 개수 (k=0, 1)

이 문제는 k에 올 수 있는 수가 0 또는 1 두 가지 경우이므로 생각해보기가 더 쉬웠다.

먼저 N=1 일때 이친수는 0으로 시작할 수 없다고 했으므로 d[1][1] = 1 , d[1][0] = 0 으로 정의된다. 

2자리부터 차근차근 생각해보면 다음과 같다. 

 1이 연속으로 나오면 안되기 때문에 1로 끝나는 N-1자리 이친수가 N자리 이친수가 되기 위해서는 0만 올 수 있다. 0으로 끝나는 N-1자리 이친수 다음에는 0, 1 어떤 것이 와도 N자리 이친수가 된다. 점화식으로 나타내면 다음과 같다.

Ⅰ. d[N][0] = d[N-1][0] + d[N-1][1]

Ⅱ. d[N][1] = d[N-1][0]

구하고자 하는 답은 N자리 이친수의 개수 즉, Ⅰ+Ⅱ이다. 

제출했을때도 한번에 정답을 맞출 수 있었다.

<전체코드>

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

public class _2193 { 

	static long[][] d;
	static int n;
	static long ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		d = new long[n+1][2];
		
		d[1][0]=0;
		d[1][1]=1;
		
		for(int i=2;i<=n;i++) {
			d[i][0] = d[i-1][0] + d[i-1][1];
			d[i][1] = d[i-1][0];
		}
		
		ans = d[n][0] + d[n][1];
		System.out.println(ans);
	}

}