[BOJ 2193] 이친수 (Java, DP)

 

---

문제 링크 

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

2193번: 이친수

---

문제 풀이 

- 시간복잡도 : O(N)

- 점화식 DP[N] = DP[N - 2] + DP[N - 1] 형태로 최대 N이 90까지 가능하다

- 피보나치의 경우 46번째만 넘어가도 29억이 넘기 때문에 long (8byte, 64bit)으로 문제 풀이 해야 함

 

풀이 순서
가짜 문제 정의 - 가짜 문제로 정답을 구할 수 있는가? - 초기항 - 점화식 - 풀이 & 테스트

0	1	2	3	4
0	1	10	100 101	1000 1010 1001

- 초기항의 경우 DP[0] = 0, DP[1] = 1로 해준다 

- DP[N - 1] 숫자에 대해 뒤에 '0'을 붙이고, DP[N - 2]에 대해 뒤에 '01'을 붙이게 되면 중복 없이 숫자 구할 수 있다

 

 

---

제출 코드 

 

(1) Bottom-Up방식 

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

public class Main {
    
    static int N;

    static long[] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        DP = new long[N + 1];
    }

    static void executeBottomUp() {
        DP[0] = 0;
        DP[1] = 1;

        for(int i = 2; i <= N; i++) {
            DP[i] = DP[i - 1] + DP[i -2];
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        executeBottomUp();

        System.out.println(DP[N]);
    }
    
}

 

(2) Top-Down 방식

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

public class Main {
    
    static int N;

    static long[] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        DP = new long[N + 1];
        
        Arrays.fill(DP, -1);
        DP[0] = 0L;
        DP[1] = 1L;
    }

    static long topDown(int idx) {
        if(idx == 0 || idx == 1) return DP[idx];

        if(DP[idx] != -1) return DP[idx];

        return DP[idx] = topDown(idx - 2) + topDown(idx - 1);
    }

    public static void main(String[] args) throws Exception {
        input();

        System.out.println(topDown(N));
    }
}