개요

https://www.acmicpc.net/problem/9095
정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

접근 방식

1. 3을 뒤에 사용하든 앞에 사용하든 상관이 없는 문제이므로
   3부터 사용하고 남은 값 조사하는 식으로 구현했다.

2. 3을 최대로 사용할 수 있는 갯수는 숫자를 3으로 나눈 몫의 값과 동일하다.
   따라서 최대로 사용할 수 있는 갯수부터 0개까지 반복을 했다.

      // 3을 최대 개수부터 0개까지 사용했을 때 반복문
      for (int i = amount3; i >= 0; i--)
      {

3. 사용한 갯수만큼 cur값에서 빼줬다. 남은 cur값을 또 2로 나눠
   2를 사용할수 있는 최대 갯수를 구했고, 반복문을 통해 2를 사용할 수 있는 모든 경우를 계산했다.

       for (int i = amount3; i >= 0; i--)
     {
         int cur = N;
         cur -= i * 3;
         used3 = i;
         amount2 = cur / 2;
         //3을 i개만큼 사용하고 남은 수에서 2를 최대 갯수부터 0개 까지 사용했을 때 반복문
         for (int j = amount2; j >= 0; j--)
         {
             int tmp = cur;
             tmp -= j * 2;
             used2 = j;
             //2사용하고 남은 숫자가 곧 1의 갯수
             used1 = tmp;

4. 이제 각 케이스에서 몇 개의 1,2,3을 사용햇는지 구했으므로 해야할 일은
   같은 원소를 가진 순열의 경우의 수를 구하면 된다.
   1이 n개 2가 m개 3이 k개 있다고 하면
   나올 수 있는 수열의 갯수는
   (n+m+k)! / (n! * m! * k! )이다.

전체 코드

#include<iostream>
using namespace std;

int HowManyWays(int N) {
    // 3을 사용할수 있는 최대 갯수
    int amount3 = N / 3, usedNum = 0, amount2, used3 = 0, used2 = 0, used1 = 0;
    // 3을 최대 개수부터 0개까지 사용했을 때 반복문
    for (int i = amount3; i >= 0; i--)
    {
        int cur = N;
        cur -= i * 3;
        used3 = i;
        amount2 = cur / 2;
        //3을 i개만큼 사용하고 남은 수에서 2를 최대 갯수부터 0개 까지 사용했을 때 반복문
        for (int j = amount2; j >= 0; j--)
        {
            int tmp = cur;
            tmp -= j * 2;
            used2 = j;
            //2사용하고 남은 숫자가 곧 1의 갯수
            used1 = tmp;

            //같은 원소를 가진 순열 계산
            int allMul = 1, Mul3 = 1, Mul2 = 1, Mul1 = 1;
            for (int k = 1; k <= used3 + used2 + used1; k++)
            {
                allMul *= k;
            }
            for (int k = 1; k <=used3; k++)
            {
                Mul3 *= k;
            }
            for (int k = 1; k <= used2; k++)
            {
                Mul2 *= k;
            }
            for (int k = 1; k <= used1; k++)
            {
                Mul1 *= k;
            }
            usedNum += (allMul / (Mul3 * Mul2 * Mul1));

        }
    }
    return usedNum;
}

int main() {
    int testCase, targetNum;
    cin >> testCase;

    for (int i = 0; i < testCase; i++) {
        cin >> targetNum;
        cout << HowManyWays(targetNum)<<"\n";
    }
}

다른 풀이

다이나믹 프로그래밍을 이용해 풀이하면 훨씬 간단했다!
1,2,3의 합을 이용해 숫자를 만드는 문제이므로
점화식은 d[n] = d[n-1]+d[n-2]+d[n-3]이다.
풀이하면 n을 만들기위한 경우의 수는
(n-1을 만드는 경우의 수) +(n-2를 만드는 경우의 수) + (n-3을 만드는 경우의 수) 와 같다.

이유는 n-1을 만드는 각각의 경우에 대해 1을 더한 값 +
n-2를 만드는 각각의 경우에 대해 2를 더한 값 +
n-3을 만드는 각각의 경우에 대해 3을 더한 값이
n을 만드는 모든 경우이기 때문이다.

다른 풀이 코드

#include<iostream>
using namespace std;
int dp[12];
void Init(){
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    for(int i=4;i<=11;i++){
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
}

int main()
{
    int T, targetNum;
    cin >> T;
    Init();
    for (int i = 0; i < T; i++)
    {
        cin >> targetNum;
        cout << dp[targetNum] << "\n";
    }
}