[C++] 백준 9095 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

1. 서론

 

순열조합 문제 풀라고 푼 문제... DP라고 분류되어 있어서 메모리 터질까 봐 걱정했는데 안 터졌다... ㅎㅎ 역시나 쉬운 문제

 

2. 문제 풀이

 

정수 n이 주어진다. 이를 1, 2, 3의 조합으로 합을 구해서 n이 되도록 하는 경우의 수를 구하는 문제이다.

 

예제를 딱 보니 중복순열이었다. 1, 2, 3을 중복으로 사용해도 되고 1 + 1 + 2와 1 + 2 + 1이 다른 경우이므로 순열이기 때문에!

하지만 몇 개를 뽑는지는 정해져 있지 않기 때문에 제일 많이 뽑는 모든 수가 1이었을 때 경우부터 숫자 하나만 뽑는 경우, 즉 n~1의 범위만큼 뽑기를 진행해줬다. 그리고 재귀를 돌리면서 그 배열들의 합이 n인지 아닌지를 체크하고 맞으면 카운트해줬다.

 

3. 코드 설명

 

#include <iostream>

using namespace std;

int cnt = 0, n;

void perm(int a[], int p[], int d, int x)
{
    if (d == x)
    {
        int sum = 0;

        for (int i = 0; i < d; i++)
            sum += p[i];

        if (sum == n)
            cnt++;

        return;
    }

    for (int i = 0; i < 3; i++)
    {
        p[d] = a[i];
        perm(a, p, d + 1, x);
    }
}

int main()
{
    int t, i, j;

    cin >> t;

    for (i = 0; i < t; i++)
    {
        cin >> n;

        int a[] = {1, 2, 3};
        
        for (j = n; j > 0; j--)
        {
            int p[j];
            perm(a, p, 0, j);
        }

        cout << cnt << endl;
        cnt = 0;
    }
}

 

값을 입력받고 perm 함수에 값을 넘긴다. 근데 이때 위에서 설명한 것처럼 n~1까지 뽑기를 진행해야 하기 때문에 반복문 및 변수 추가.

perm 함수는 중복순열을 구현한 함수!!

(DP로는 어떻게 푸는지 궁금만 하네 ㅎ)