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

 

---

문제 링크

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

9095번: 1, 2, 3 더하기

---

문제 풀이

- 시간복잡도 O(N)

- DP 상향식 문제 

 

*절차

(1) 가짜 문제 정의

진짜 문제 = 주어진 N에 대해 N을 1,2,3의 합으로 표현하는 경우의 수 

가짜 문제 = DP[i] 를 1,2,3으로 표현하는 경우의 수 

(2) 가짜 문제를 풀면 진짜 문제를 풀 수 있는가 ? YES

(3) 초기항 정의 

0	1	2	3
0	1	2 ( 1 + 1, 2)	4 - 0에 3을 더할 경우 - 1에 2를 더할 경우 - 2에 1을 더할 경우

(4) 점화식 세우기 

DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3]

---

제출 코드

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

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

    static int T;

    static int[] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        DP = new int[12];
        DP[0] = 0;
        DP[1] = 1;
        DP[2] = 2;
        DP[3] = 4;

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

        while(T > 0) {
            T -= 1;

            int N = Integer.parseInt(br.readLine());
            sb.append(DP[N]).append("\n");
        }

    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
}