누적합배열

박진은·2024년 1월 8일

Resource

목록 보기

4/20

tags:

DP
last updated:
due date:
Project:
aliases:

tasks

[! Todo] Title
https://www.acmicpc.net/problem/9095

background Information

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

Study

package run;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  
  
public class Main {  
    public static int solution(int n){  
        if(n <= 3){  
            if(n == 1){  
                return 1;  
            }  
  
            if(n == 2){  
                return 2;  
            }  
  
            if(n == 3){  
                return 4;  
            }  
        }  
  
        int[] dp = new int[n+1];  
        dp[1] = 1;  
        dp[2] = 2;  
        dp[3] = 4;  
  
        for (int i = 4; i <=n; i++) {  
            int sum = 0;  
            for (int j = i-3; j < i; j++) {  
                sum += dp[j];  
            }  
            dp[i] = sum;  
        }  
        return dp[n];  
    }  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int t = Integer.parseInt(br.readLine());  
        int[] answer = new int[t];  
        for (int i = 0; i < t; i++) {  
            answer[i] = solution(Integer.parseInt(br.readLine()));  
        }  
        for (int i = 0; i < t; i++) {  
            System.out.println(answer[i]);  
        }  
    }  
}