[백준] 2193번 이친수

1) 생각

첫 번째 생각

시작이 '0'이 될 수 없으므로 시작은 무조건 '1'로 한다. 그 이후에 가장 마지막 값을 확인해서 0일 때만 0과 1 둘을 붙여서 계속 탐색하고 마지막 값이 '1'일 경우에는 0만 붙여서 탐색하였다.

'시간초과'의 결과가 나왔다.

두 번째 생각

간단한 문제이므로 알고리즘에는 잘못이 없다 생각하였고 몇 가지 Case를 적어보자 n = n-1 + n-2라는 피보나치의 점화식이 보여 DP를 적용하여 풀었다.

2) 방안

기존의 재귀를 이용한 완전 탐색을 DP를 적용하여 반복문을 이용하여 풀었다.

N의 값이 커질경우 int형 범위를 넘어가 Overflow가 발생하므로 long 타입으로 해결하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
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[91];
        dp[1] = 1;
        dp[2] = 1;
        solve(n);
        System.out.println(dp[n]);
    }
    
    private static void solve(int idx) {
        if(idx<3) return;
        for(int i=3;;i++) {
            dp[i] = dp[i-1]+dp[i-2];
            if(i==n) break;
        }
    }
}