백준 2193번 - 이친수

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

2193번: 이친수

 

 

 

다음 문제는 경우의 수를 모두 작성하여 규칙을 본 결과 피보나치 배열과 같다는 걸 알게 되었다.

 

 

N자리 이친수의 개수는 다음과 같다.

 

 

코드

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

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[N+1];
        dp[0]=0;
        dp[1]=1;
     
        for(int i=2;i<=N;i++)
        {
        	dp[i]=dp[i-1]+dp[i-2];
        }
        System.out.println(dp[N]);
    }
}