[Silver3-JAVA] 백준 2193 - 이친수

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

2193번: 이친수

 

 

🤔문제 풀이

간단한 DP 문제였다.

이친수는 첫째 자리가 반드시 1로 시작해야하며 1이 연속으로 오지 않는 수인데

자릿수가 증가할때마다 가능한 숫자들의 개수를 구해보니

N=1일때, 1 (1개)

N=2일때, 10 (1개)

N=3일때, 100, 101 (2개)

N=4일때, 1000, 1001, 1010 (3개) ...

 

dp[N] = dp[N-1] + dp[N-2]의 피보나치 수열의 형태를 띄는 것을 알 수 있었다.

따라서 N=2까지 초깃값을 dp배열에 저장하고 이후 위의 점화식을 이용해 N=3부터 구하고자하는 N자리까지

구한 뒤 dp[N]을 결과로 출력하도록 했다.

 

🚨CODE

import java.io.*;
import java.util.*;

public class Main {
	static long[] dp;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		dp = new long[n+2];
		dp[0] = 0;
		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]);
	}

}