[실버3, DP] 백준 9095 - 1, 2, 3 더하기 (자바)

Think

1. DP 분류로 되어있는 문제로 고른거였지만, DP로 풀 방법이 떠오르지 않아 처음에는 단순 재귀로 풀었다.

2. https://lotuslee.tistory.com/43 를 참고해보니, 규칙성이 있다는 점을 확인할 수 있었고, 이를 통해 점화식을 도출하는 부분을 보았다.

3. https://goodmilktea.tistory.com/43 의 글처럼, DP는 (재귀를 적용시킬 점화식) + (종료조건)을 찾는게 관건인 것 같다.

4. 앞으로도 Top-Down과 Bottom-Up 방식을 모두 고려해보자

 

제출 코드1 (DP)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class test {
    static int n, t,count;
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
    }

    private static void progress() {

//        System.out.println(topDownDP(n));
        bottomUp();
    }

    private static int topDownDP(int number) {
        if(dp[number] == null){
            dp[number] = topDownDP(number-1) + topDownDP(number-2) + topDownDP(number-3);
        }

        return dp[number];
    }

    private static void bottomUp(){
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        System.out.println(dp[n]);
    }


    private static void init() throws IOException {
        t = Integer.parseInt(br.readLine());
        dp = new Integer[11];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());

            progress();
        }
    }

}

 

 

제출코드 2 (단순 재귀)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, t,count;
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
    }

    private static void progress() {

        recursion(0);
        System.out.println(count);

    }

    private static void recursion(int sum) {
        if(sum == n){
            count++;
            return;
        }

        if(sum+1 <= n) recursion(sum+1);
        if(sum+2 <= n) recursion(sum+2);
        if(sum+3 <= n) recursion(sum+3);
    }


    private static void init() throws IOException {
        t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());

            count=0;
            progress();
        }
    }

}