[백준 2193] 이친수

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

DP문제입니다.

일단 이걸 직접 손으로 좀 써내려가다보면 피보나치 수열이 나오긴 합니다만... 

그냥 문제에 적힌 그대로 풀었습니다. 결과적으로는 비슷하다고 해야하나 같다해야하나 그렇습니다.

일단

1자리 수는 1밖에 없음.

2자리 수는 1 - 0 밖에 없음

3자리 수는 1 - 0 - 0

               1 - 0 - 1 존재.

4자리 수는   3자리수 맨뒤 0 -> 0, 1   2가지 가능

                 3자리수 맨뒤 1 -> 0      1가지 가능.  총 3가지 가능

 

그림으로 보면서 정리하면

 

현재 자리수( D[0][N] + D[1][N] ) 의 이천수의 갯수를 구하기 위해선

 D[0][N] = D[0][N-1] + D[1][N-1]      

 D[1][N] = D[0][N-1]

두 개의 값을 구해 더하면 됩니다.

 

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