BOJ 2193 - 이친수

입력

• N 입력 (1 ≤ N ≤ 90)

출력

• N자리 이친수의 개수 출력

풀이 방법

• N이 2일 때 이친수는 10으로, 1개
• N이 3일 때 이친수는 101, 100으로, 2개
• N이 4일 때 이친수는 1001, 1010, 1000으로,

10(01) - N이 2일 때의 이친수에 01을 덧붙인 수 101(0), 100(0) - N이 3일 때의 이친수에 0을 덧붙인 수 따라서 N=4일 때의 이친수 개수는 (N=2일 때의 이친수 개수)+(N=3일 때의 이친수 개수) = 1+2 = 3

• N이 5일 때 이친수는 10101, 10001, 10010, 10100, 10000으로,

101(01), 100(01) - N이 3일 때의 이친수에 01을 덧붙인 수 1001(0), 1010(0), 1000(0) - N이 4일 때의 이친수에 0을 덧붙인 수 따라서 N=5일 때의 이친수 개수는 2+3 = 5

• 이를 일반화하면,

(N자리 이친수의 개수) = ((N-1)자리 이친수의 개수) + ((N-2)자리 이친수의 개수)

코드

import java.util.Scanner;

public class BOJ_2193 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();	// 자연수 N 입력
		
		long[] dp=new long[91];
		dp[1]=1;
		dp[2]=1;
		
		for(int i=3;i<=N;i++) {	// 다이나믹 프로그래밍
			dp[i]=dp[i-1]+dp[i-2];
		}
		
		System.out.println(dp[N]);
	}
}