[JAVA] 백준 2193번- 이친수

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

2193번: 이친수

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

       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]);
    }
}

 

 

그냥 하나씩 따져보다보면 눈치챌 수 있다.

 

 

dp[n] = n자리 이친수의 개수
dp[n] = dp[n-1]+dp[n-2]

 

dp[1] = 1

dp[2] = 10

dp[3] = 100, 101

dp[4] = 1000, 1010, 1001

 

 

맨앞자리가 0이 되면 안되고 1이 연속으로 올 수 없다.

그러므로 앞의 두자리는 무조건 10이여야만 한다.

 

그 다음부터 10을 제외한 n자리수의 마지막 n-2개의 숫자는 n-2, n-1자리 수의 마지막 n-2개의 숫자와 같다.

 

 

주의해야할 점은 피보나치수는 46항쯤이 되면 int범위를 초과해버리기 때문에 이문제의 범위인 90번째까지 구하려면 long을 써야 한다.