[백준-2193번] 이친수 풀이 - Java

🚀 문제

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

 

🚀 접근 방법

 DP 문제이다.

주의할 점은 long으로 선언해야 된다는 점 -> n이 커지면 이친수 값이 int를 벗어날 수 있음

 

규칙은 dp[i] = dp[i-1]+dp[i-2]

1	2	3	4	5
1	10	101 100	1010 1000 1001	10101 10100 10000 10001 10010

 

🚀 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());

        long[] dp = new long[n+1];

        if(n>=1)
            dp[1] = 1;
        if(n>=2)
            dp[2] = 1;

        for(int i=3; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

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