[058] 9095. 1,2,3 더하기

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

9095번: 1, 2, 3 더하기

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하기

- 합을 나타낼 때에는 수를 1개 이상 사용해야 한다.

 

 

🧶 풀이과정 

 

쉬운 dp 문제인데, 역시 나는 숫자를 써가면서 정리했다.

 

1 ) 1

2) 1+1 , 2

3) 1+1+1, 1+2, 2+1, 3

 

여기서 보면 대에충 감이 오는데,  0을 1이라고 할 경우에(왜냐면 1, 2, 3은 0+각각의 수)

2는 1에 1을 더하고, 0에 2를 더하는 2개.

3은 1에 + 2, 2에 +1, 1+1에 +1, 0에 +3을 하는 4개라는 것을 알 수 있다.

 

여기에서는 1,2,3 세가지이기 때문에 점화식은 결국

dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 이 될 것이다.

 

만약, 이 수가 넘어가서 1,2,3,4라면

dp[n] = dp[n-4] + dp[n-3] + dp[n-2] dp[n-1] 이 될 거라고 생각하면 됨.

 

 

 

🏹 제출코드

package data_structure_part_01;

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

public class Q9055 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

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

            int[] dp = new int[11];

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

            for(int j = 4; j <= n; j++){

                dp[j] = dp[j-3] + dp[j-2] + dp[j-1];
            }

            System.out.println(dp[n]);
        }

        br.close();
    }
}