이친수

📍 문제 설명

 

💡 접근

1자리일 때 1 -- 1

2자리일 때 1 -- 10

3자리일 때 2 -- 100 101

4자리일 때 3 -- 1000 1001 1010 

5자리일 때 5 -- 10000 10001 10010 10100 10101

피나보치 문제다.

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static long[] arr, dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = kb.nextInt();
        dp = new long[n+2];
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }

        System.out.println(dp[n]);

    }

    private void solution() {
    }

}