[DP]백준 9095 1, 2, 3 더하기 & 15988 1, 2, 3 더하기 3

< 반복문 버전 - ac >

package DP;

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

public class boj_15988_123더하기3 {
    private static int testcaseNumber, dp[], testcaseArr[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testcaseNumber = Integer.parseInt(br.readLine());
        testcaseArr = new int[testcaseNumber];

        int max = -1;
        for (int i = 0; i < testcaseNumber; i++) {
            testcaseArr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, testcaseArr[i]);
        }
        dp = new int[max+4];
        dp[0] = 1;

        calc(max);

        for (int i = 0; i < testcaseNumber; i++) {
            System.out.println(dp[testcaseArr[i]]);
        }
    }

    private static void calc(int max) {
        for(int i = 0; i <= max; i++){
            for(int j = 1; j <= 3; j++){
                dp[i+j] = (dp[i+j] + dp[i]) % 1000000009;
            }
        }
    }
}

< 반복문 - 코드 길이 줄인 버전 >

package DP;

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

public class boj_15988_123더하기3 {
    private static int testcaseNumber, dp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testcaseNumber = Integer.parseInt(br.readLine());

        calc();

        for (int i = 0; i < testcaseNumber; i++) {
            System.out.println(dp[Integer.parseInt(br.readLine())]);
        }
    }

    private static void calc() {
        dp = new int[1000004];
        dp[0] = 1;

        for(int i = 0; i <= 1000000; i++){
            for(int j = 1; j <= 3; j++){
                dp[i+j] = (dp[i+j] + dp[i]) % 1000000009;
            }
        }
    }
}

< 재귀버전 - 시간초과 >

package DP;

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

public class boj_15988_123더하기3_야옹스쿨 {
    private static int T, dp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        dp = new int[1000001];

        for (int i = 0; i < 1000001; i++) {
            dp[i] = -1;
        }
        for (int i = 0; i < T; i++) {
            System.out.println(recur(Integer.parseInt(br.readLine())));
        }
    }

    private static int recur(int total) {
        if(total < 0) return 0;

        if(total == 0) return 1;

        if(dp[total] != -1) return dp[total];

        int ret = 0;

        for (int i = 1; i <= 3; i++) {
            ret = (ret + recur(total - i)) % 1000000009;
        }
        dp[total] = ret;

        return dp[total];
    }
}

 

재귀 버전으로 돌리려다보니까 시간초과가 나버렸다. 아무래도 호출을 할 때 시간이 많이 걸렸던 것으로 보인다. DP 접근법은 템플릿 적용 -> 백트래킹 -> 메모이제이션 후에 점화식 도출하고 for문으로 처리하면 좋을 것 같다.