[Java] 백준 2193번 이친수

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

2193번: 이친수

 

풀이

 

dp[N] = N자리 수일때 가질 수 있는 이친수의 개수

 

dp[1] = 1 (1)

dp[2] = 1 (10)

dp[3] = 2 (101, 100)

dp[4] = 3 (1000, 1001, 1010)

dp[5] = 5 (10000, 10001, 10010, 10101, 10100)

...

 

여기서 알 수 있는 규칙은 이친수는 11을 부분 문자열로 갖지 않기때문에 무조건 10으로 시작한다는 것이다.

또한 위에서 알 수 있는 점화식은 dp[N] = dp[N-1]+dp[N-2] 이다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
		
		int N = s.nextInt();
		long dp[] = new long[N+1];
		
		//초기화
		dp[0] = 1; dp[1] = 1;  
		
		for(int i=2; i<N; i++) {
			dp[i] = dp[i-1]+dp[i-2];
		}
		
		System.out.print(dp[N-1]);
	}
}