2193_이찬수

사용 알고리즘: dp

사용 언어: java

 

package week30;

import java.io.*;
import java.util.*;
public class MM {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
//		int[] dp = new int[n+1];
//		dp[1] = 1; //1
//		dp[2] = 1; //10
//		dp[3] = 2; //100 101
//		dp[4] = 3; //1000 1010 1001
//		dp[5] = 5; //10000 10100 10010 10001 10101
//		dp[6] = 8; //100000 101000 100100 100010 101010 
					//100001 101001 100101
		//내가 홀수, 앞이 짝수면
		//앞의 개수에 0붙이는 건 무조건 가능.
		//앞 수 중 1로 끝나면 1을 붙이기 불가능
		long[] dp0 = new long[n+1];
		long[] dp1 = new long[n+1];
		dp0[1]=0; dp1[1]=1;
//		dp0[2]=1; dp1[2]=0;
//		dp0[3]=1; dp1[3]=1;
		for(int i=2; i<=n; i++) {
			dp0[i] = dp0[i-1] + dp1[i-1];
			dp1[i] = dp0[i-1];
		}
		
		System.out.println(dp0[n]+dp1[n]);
		sc.close();

	}

}

 

점화식을 찾기 위해 노력하 흔적...

그런데 dp배열 하나만으로는 점화식을 이해하기 어려웠다.

그래서 i의 자리 이진수일 때, 0으로 끝나는 이진수의 개수를 저장하는 dp0과 1로 끝나는 이진수의 개수를 저장하는 dp1을 두개 만들었다.

 

DP문제의 대표격인 종이 붙이기였나..? 그 문제랑 비슷하다고 생각하면 될 거 같다.

i-1자리 이진수가 뭐로 끝나든 0은 다~ 붙일 수 있다.

따라서 dp0[i] 는 dp0[i-1]과 dp1[i-1]을 더한 값이다.

 

또한 i-1자리 이진수 중, 0으로 끝나는 애들만 뒤에 1을 붙일 수 있다.

따라서 dp1[i]는 dp0[i-1]의 개수와 같다.

 

결과적으로 i자리 이진수에서 만들 수 있는 이찬수는

dp0[i] + dp1[i] 개가 된다.

 

이거!!! long타입 사용해야 한다...