BOJ-백준 9095번 1,2,3 더하기 C++

BOJ-백준 9095번 1,2,3 더하기 C++ 문제 풀이 입니다.

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

9095번: 1, 2, 3 더하기

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
using namespace std;
// 알고리즘 분류 다이나믹 프로그래밍


int n;
int fact[12];
int factorial(int x){
  if (x==0 || x == 1) return fact[x] = 1;
  else if (fact[x]==0) return x*factorial(x-1);
  else return fact[x];
}

int cal(int a, int b, int c){
  int s = a+b+c;
  int samethings = factorial(a) * factorial(b) *factorial(c);
  return factorial(s)/samethings;
}

int main() {
  int t;
  cin>>t;
  while(t--){
  cin>>n;
  //1,2,3으로 가능한 조합 중 합이 n이 되면 count
  //n은 11 보다 작다.
  int result =0;
  for(int x=0; x<=n; x++){
    for(int y=0; y<=n/2; y++){
      for(int z=0; z<=n/3; z++){
        int sum = 1*x + 2*y +3*z;
        if(sum == n){
          //cout<<"1*"<<x<<" + 2*"<<y<<" + 3*"<<z<<endl;
          result += cal(x,y,z);
        }
      }
    }
  }
  cout<<result<<endl;
  }
  
}

 

📌 해설

다이나믹 프로그래밍 문제입니다. 1, 2, 3의 조합으로 입력받은 정수 N을 나타내는 방법의 총 가지 수를 구하는 문제입니다. 순열 개념이 사용되므로 factorial을 구현하여 문제를 풀 수 있었습니다. 입력되는 수 n은 양수이며 11보다 작습니다. 그래서 삼중 for문을 사용하고, factorial 이 재귀적으로 호출할 수 있었습니다. 

만약 n = 5 이면, 

1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1

1 + 2 + 2 2 + 1 + 2 2 + 2 + 1

3 + 1 + 1 1 + 3 + 1 1 + 1 + 3

2 + 3 3+ 2

총 13가지의 경우의 수가 존재합니다.

1,2,3은 중복되어 선택될 수 있으므로 같은것이 있는 순열로 접근하여 문제를 해결할  수 있습니다. 

즉, 해당 경우의 수를 1이 선택된 횟수, 2가 선택된 횟수, 3이 선택된 횟수로 나누어 아래 표와 같이 표현 할 수 있습니다.

1 + 1 + 1 + 1 + 1	1*5 + 2*0 + 3*0
1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1	1*3 + 2*1 + 3*0
1 + 2 + 2 2 + 1 + 2 2 + 2 + 1	1*1 + 2*2 + 3*0
3 + 1 + 1 1 + 3 + 1 1 + 1 + 3	1*2 + 2*0 + 3*2
2 + 3 3+ 2	1*0 + 2*1 + 3*1

가령, 1*2 + 2*0 + 3*2의 경우 1 1 3 을 줄 세우는 방법의 수를 구하는데 1은 같은게 2개 있으므로

3! / 2! 으로 같은 것이 있는 순열 문제로 바꾸어서 경우의 수를 구할 수 있습니다. 

#include <iostream>
using namespace std;
// 알고리즘 분류 다이나믹 프로그래밍

int n;
int fact[12];

1. 필요한 변수를 전역으로 선언합니다. factorial 값을 저장하여 효율적으로 factorial값을 사용하도록 했습니다. 

 

int factorial(int x){
  if (x==0 || x == 1) return fact[x] = 1;
  else if (fact[x]==0) return x*factorial(x-1);
  else return fact[x];
}

2. factorial을 계산하는 함수

2-1. 팩토리얼을 계산하기 위한 함수입니다. x가 0 혹은 1일 경우 1을 반환합니다. 

2-2. 팩토리얼이 아직 계산되지 않았다면 factorial을 재귀호출합니다. 

2-3. 팩토리얼 값이 존재한다면 해당 값을 배열에서 가져와 반환합니다. 

 

int cal(int a, int b, int c){
  int s = a+b+c;
  int samethings = factorial(a) * factorial(b) *factorial(c);
  return factorial(s)/samethings;
}

3. 경우의 수를 계산하는 cal함수

3-1. 1의 개수 a, 2의 개수 b, 3의 개수 c 를 매개변수로 받아와 총 합을 s에 저장합니다. 

3-2. 같은 것이 있는 순열을 구해야 하므로 a! * b! * c! 을 samethings에 저장합니다. 

3-3. (a+b+c)! / a! * b! * c! 으로 1, 2, 3 의 순열을 구하는 것으로 총 가지 수를 구하여 리턴합니다. 

 

int main() {
  int t;
  cin>>t;
  while(t--){
  cin>>n;
  //1,2,3으로 가능한 조합 중 합이 n이 되면 count
  //n은 11 보다 작다.
  int result =0;
  for(int x=0; x<=n; x++){
    for(int y=0; y<=n/2; y++){
      for(int z=0; z<=n/3; z++){
        int sum = 1*x + 2*y +3*z;
        if(sum == n){
          //cout<<"1*"<<x<<" + 2*"<<y<<" + 3*"<<z<<endl;
          result += cal(x,y,z);
        }
      }
    }
  }
  cout<<result<<endl;
  }
  
}

4. main

4-1. 테스트케이스 수, n 값을 입력 받습니다. 

4-2. result를 0으로 초기화 하고 선언합니다. 

4-3. 삼중 for문을 작성합니다. 연산횟수를 줄일 수 있도록 y는 n/2번 까지, z는 n/3번 까지 돌 수 있도록 합니다. 

( n = 10 일 경우, 1은 최대 10번 선택될 수 있으나, 2는 최대 5번, 3은 최대 3번 까지 선택 가능합니다. 따라서 2와 3이 선택될때 n만큼 돌릴 필요가 없습니다. )

4-4. 1*x + 2*y +3*z 의 값이 n이 되면 cal함수를 호출하여 같은 것이 있는 순열을 구해 result에 합산합니다. 

4-5. 삼중 for문이 종료되면 result를 출력합니다. 

 

 

 

 

::