[백준] 2193번 이친수

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

2193번: 이친수

 

	1	2	3	4	5	6	7
0		10	100	1000 1010	10000 10010 10100	100000 100010 100100 101000 101010	1000000 1000010 1000100 1001000 1001010 1010000 1010010 1010100
1	1		101	1001	10001 10101	100001 100101 101001	1000001 1000101 1001001 1010001 1010101

dp[6][0] = dp[5][0] + dp[5][1] : dp[5] 와 같음

dp[6][1] = dp[5][0] : dp[4] 와 같음

 

dp[6] = dp[5] + dp[4] 

점화식 : dp[N] = dp[N-1] + dp[N-2]

 

 

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

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        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]);
    }
}