[10일차][dp2] 4개의 수

- 문제 설명

3개의 숫자를 이용해 4번째 숫자를 만족하는 경우의 수를 구하기

1,2,3이 주어지고 4를 만족하려면

1+1+1+1

1+1+2

2+1+1

1+2+1

2+2

1+3

3+1

위와 같이 총 7가지가 있다.

- 입력

1 // 테스트 케이스

1 2 3 4 // 1,2,3이 주어지고 4를 만들기

- 출력

#1 7 // 테스트케이스, 4번째 숫자를 만드는 중복순열의 경우의 수

- 입력 예시

3
1 2 3 4
1 2 3 7
1 2 5 15

- 출력 예시

#1 7
#2 44
#3 1843

- 코드

#include "stdio.h"

int input[3];

int goalSum;

int numOfCombination[21];

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        scanf("%d %d %d",&input[0],&input[1],&input[2]); // 숫자 3개 입력 받음

        scanf("%d",&goalSum); // 목표 합 입력 받음

        

        for(int i=0;i<=goalSum;i++)

        {

            numOfCombination[i] = 0; // 조합 갯수 초기화

        }

        for(int i=0;i<3;i++) // 처음 입력받은 애들로 입력받은 숫자를 만드는 경우의 수는 1

        {

            numOfCombination[input[i]] = 1;

        }

        for(int i = input[0] + 1 ; i <= goalSum; i++) // 입력받은 숫자중 가장 작은 수 다음부터 목표 숫자까지 반복

        {

            if(i - input[0] >= 1) // input[0] 즉 첫번째 숫자를 더해서 i를 만드는 경우

            {

                numOfCombination[i] += numOfCombination[i-input[0]]; // x + 첫번째 숫자 = i 인 경우이므로 x의 경우의 수를 현재 경우의 수 배열에 더해준다.

            }

            

            if(i - input[1] >= 1) // input[1] 즉 두번째 숫자를 더해서 i를 만드는 경우

            {

                numOfCombination[i] += numOfCombination[i-input[1]]; // x + 두번째 숫자 = i 인 경우이므로 x의 경우의 수를 현재 경우의 수 배열에 더해준다.

            }

            if(i - input[2] >= 1) // input[2] 즉 세번째 숫자를 더해서 i를 만드는 경우

            {

                numOfCombination[i] += numOfCombination[i-input[2]]; /// x + 세번째 숫자 = i 인 경우이므로 x의 경우의 수를 현재 경우의 수 배열에 더해준다.

            }

            

        }

        printf("#%d %d\n",tc,numOfCombination[goalSum]);

    }

    return 0;

}