백준 2193 : 이친수 _자바 Java

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

2193번: 이친수

 

---

n=1 : 0 1 =>1
n=2 : 00 01 10 11 =>1
n=3 : 000 001 010 100 
         011 110 101 111 => 2
n=4 : 0000 0001 0010 0100 1000
         0011 0101 1010 1001 1100
         0111 1011 1101 1110

         1111 => 3
 

dp[i]= dp[i-2]+dp[i-1]

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-2]+dp[i-1]);
		}
		System.out.println(dp[n]);
		

	}
	
}