백준 15990번 1,2,3더하기 5 (JAVA)

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

15990번: 1, 2, 3 더하기 5

해당 문제는 저는 재귀적인 DP를 활용하여 문제를 해결하였습니다.

저는 인자로 구하고자하는 값과 시작하는 숫자를 주었습니다.

dp[구하고자하는 값][시작하는 숫자] = 시작하는 숫자로 시작하는 구하고자하는 값의 개수 입니다.

이를 통해 구하고자하는 값의 경우의 수 = dp[구하고자하는 값][1] + dp[구하고자하는 값][2] + dp[구하고자하는 값][3]로 최종 값을 구하였습니다.

 

 

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15990 {
    static final int LIMIT = 1_000_000_009;
    static private int dfs(int[][] dp , int n,int start){
        if(n <= 0){
            return 0;
        }
        if(dp[n][start] != -1 ){
            return dp[n][start];
        }else{
            int result = 0;
            for(int i = 1 ; i <= 3 ; i++){
                if(start != i){
                    result += dfs(dp,n-start,i);
                }
            }
            result %= LIMIT;
            dp[n][start] = result;
            return dp[n][start];
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int test = stoi.apply(st.nextToken());
        int[][] dp = new int[100_000+1][4];

        for(int i = 0 ; i <= 100_000 ; i++){
            Arrays.fill(dp[i],-1);
        }

        dp[1][1] = 1; // 1
        dp[2][2] = 1; // 2
        dp[3][1] = 1; // 1 + 2
        dp[3][2] = 1; // 2+ 1
        dp[3][3] = 1; // 3

        for(int t = 0 ; t < test ; t++){
            st = new StringTokenizer(br.readLine()," ");
            int n = stoi.apply(st.nextToken());
            int result = 0;
            for(int i = 1 ; i <= 3; i++){
                result += dfs(dp,n,i);
                result %= LIMIT;
            }
            System.out.println(result);
        }
    }
}