[java] 2193번 이친수

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

1
1

2
10

3
101
100

4
1000
1001
1010

5
10000
10001
10010
10100
10101

로, dp[i] = dp[i-1] + dp[i-2] 의 점화식을 얻게 됨.

N이 90까지 가능하므로, int 형 조심

3. 코드

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

public class Main {

    static int N;
    static long[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new long[N+1];
        dp[0] = 0;
        dp[1] = 1;

        for(int i=2;i<N+1;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.println(dp[N]);
    }
}