Algorithm/Baekjoon

[Algorithm]Baekjoon 15989번 :: 1,2,3 더하기 4

MaxLevel 2024. 1. 20. 21:38

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
int t, n;
vector<int> answers;
int dp[10001][4] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    int maxNum = 0;
 
    while (t--)
    {
        cin >> n;
 
        answers.push_back(n);
        maxNum = max(maxNum, n);
    }
 
    dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
 
    for (int i = 4; i <= maxNum; ++i)
    {
        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];
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        cout << dp[answers[i]][1] + dp[answers[i]][2] + dp[answers[i]][3] << endl;
    }
}
 
 cs

 

중복되지 않으면서 1,2,3을 이용한 모든 경우의수를 구해야 하는 문제이다.

예를들어 3을 구성할 때, (1,2) 와 (2,1)은 같은 경우의 수로 취급한다.

그렇기때문에 숫자를 오름차순으로 점점 붙여나가는 식으로 생각하면 겹치지 않고 순수하게 새로운 경우의수들을 붙여나갈 수 있다.