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

1,2,3을 이용하여 수를 만드는데 중복 없이 만드는 경우의 수를 묻는 문제이다.

코드를 보면

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<memory.h>
 
using namespace std;
 
 
int d[10001];
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    cin >> testcase;
 
    int nums[3] = { 1,2,3 };
 
    d[0] = 1;
    
    for (int j = 0; j < 3; j++) {
        for (int i = 1; i <= 10000; i++) {
            if (i - nums[j] >= 0) {
                d[i] += d[i - nums[j]];
            }
        }
    }
 
    while (testcase--) {
        int n;
        cin >> n;
        cout << d[n] << endl;
    }
}

25~31번째 줄 for문이 핵심인데,

25번째 줄과 26번째 줄을 바꾸면 중복가능(1,1,2와 1,2,1를 다른것으로 치는) 경우 개수가 나온다.

중복이 가능한 경우의 점화식이

d[n] = d[n-1] + d[n-2] + d[n-3]

에서 d[n-1]과 d[n-2], d[n-3]를 먼저 구한다음 d[n]을 구하지말고

1만 써서 표현할 수 있는 개수, 2만 써서 표현할 수 있는 개수, 3만 써서 표현할 수 있는 개수를

d[n]에 각각 더해주면서 구하면 중복이 없는 경우만 뽑아 넣을 수 있게 된다.