[DP] 백준 2193 이친수 (Pinary Number)

BackJoon 

# 2193 - 이친수 (Pinary Number)

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

대표적인 DP문제입니다.

DP[N] 을 N개 자리수에 이친수를 만족하는 경우의 수라고 생각하겠습니다.

N자리에 올 수 있는 숫자는 0 OR 1입니다. 각각에 경우에 대해서 생각해 보겠습니다.

N자리에 0인 경우

N-1자리에 올 수 있는 숫자는 0 OR 1 둘 다 가능합니다. 따라서 

DP[N] = DP[N-1] 이 성립합니다.

N자리에 1인 경우

N-1자리에 올 수 있는 숫자는 0 만 가능합니다. 그렇다면 N-2 자리에 올 수 있는 숫자는? 0 OR 1 이 가능합니다. 따라서 . . .  

DP[N] = DP[N-2] 이 성립합니다.

이제 N자리에 0 이 올수도 1이 올수도 있으니 이 두 점화식을 합쳐야합니다. 결국 

DP[N] = DP[N-1] + DP[N-2] 가 성립합니다. 

이제 위 점화식 컨셉을 코드로 옮겨보면 다음과 같습니다.

package BackJoon;

import java.util.Scanner;

public class PinaryNumber {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		long dp[] = new long[n+1];
		
		dp[1] = 1;
		if(n>=2) dp[2] = 1;
		
		for(int i=3; i<=n; i++){
			//n자리가 0일경우
			//n자리가 1일경우
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		System.out.println(dp[n]);
	}

}