[BOJ 15988] 1, 2, 3 더하기 3 (Java, DP)

 

 

---

문제 링크 

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

15988번: 1, 2, 3 더하기 3

---

문제 풀이 

- 시간 복잡도의 경우 둘다 O(N)

- 최대치의 경우 long ( 나머지 연산 처리해도 N이 최대이면 범위가 넘는 듯 함)

- 피보나치에서 조금 변형된 기본 DP 문제

- 상향식, 하향식 형식 연습하기 좋은 기본 문제

 

0	1	2	3	4
0	1	1 + 1 2	1 + 1 + 1 2 + 1 3	1 + 1 + 1 + 1 2 + 1 + 1 3 + 1 1 + 1 + 2 2 + 2 1 + 3

 

점화식 

DP[i] = (DP[i - 1] + DP[i - 2] + DP[i - 3]) % MOD

마지막에 어떤 행위를 했는지 살펴보면 아래와 같다. ( 중복없음 )
- N - 1 의 경우 끝에 1을 더함
- N - 2 의 경우 끝에 2를 더함
- N - 3 의 경우 끝에 3을 더함 

---

제출 코드 

(1) Bottom-Up

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int T, N;

    static long[] DP;

    static int MOD = 1000000009;

    static void inputForBottomUp() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());

        while(T > 0) {
            T -= 1;
            N = Integer.parseInt(br.readLine());

            sb.append(DP[N]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    static void executeByBottomUp() {
        DP = new long[1000001];
        DP[1] = 1;
        DP[2] = 2;
        DP[3] = 4;

        for(int i = 4; i <= 1000000; i++) {
           DP[i] = (DP[i - 1] + DP[i - 2] + DP[i - 3]) % MOD;
        }
    }

    public static void main(String[] args) throws Exception {
        executeByBottomUp();
        inputForBottomUp();
    }
    
}

 

(2) Top-Down

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int T, N;

    static long[] DP;

    static int MOD = 1000000009;

    static void inputForTopDown() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());

        DP = new long[1000001];
        Arrays.fill(DP, -1);

        DP[0] = 0;
        DP[1] = 1;
        DP[2] = 2;
        DP[3] = 4;

        while(T > 0) {
            T -= 1;
            N = Integer.parseInt(br.readLine());

            sb.append(executeByTopDown(N)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    static long executeByTopDown(int idx) {
        if(DP[idx] != -1) return DP[idx];

        return DP[idx] = (executeByTopDown(idx - 1)
                + executeByTopDown(idx - 2)
                + executeByTopDown(idx -3)) % MOD;
    }



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