백준 15989번 1,2,3 더하기 4

카테고리 없음

백준 15989번 1,2,3 더하기 4

박카스마시며코딩 2022. 1. 14. 23:40

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

15989번: 1, 2, 3 더하기 4

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2

www.acmicpc.net

해당 문제를 DP를 이용하여 문제를 해결하였습니다.

1차원 DP를 이용하게 되면 중복이 발생하여 2차원 DP를 이용하였습니다.

저는 dp[표현하고자 하는 숫자][계산 중 최대로 작은 숫자]를 이용해 문제를 해결하였습니다.

dp[i][1] = dp[i-1][1];

dp[i][2] = dp[i-2][1] + dp[i-2][2];

dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][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_15989 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int[][] dp = new int[10_000+1][4];
        for(int i = 0 ; i <= 10_000; i++){
            Arrays.fill(dp[i],-1);
        }
        dp[1][1] = 1;
        dp[1][2] = 0;
        dp[1][3] = 0;

        dp[2][1] = 1;
        dp[2][2] = 1;
        dp[2][3] = 0;

        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;
        for(int i = 0 ; i < n ; i++){
            int num = stoi.apply(br.readLine());
            int result = 0;
            for(int j = 1 ; j <= 3; j++){
                result += cal(dp,num,j);
            }
            System.out.println(result);
        }
    }

    private static int cal(int[][] dp, int num, int start) {
        if(dp[num][start] != -1){
            return dp[num][start];
        }
        dp[num][start] = 0;
        for(int i = 1 ; i <= start ; i++){
            dp[num][start] += cal(dp,num-start,i);
        }
        return dp[num][start];
    }
}