세 개의 정수 R, G, B가 주어지고, 문자열은 오직 'R', 'G', 'B' 세 글자로만 구성됩니다. 목표는 각 글자가 최소한 R개, G개, B개씩 포함되도록 만들 수 있는 문자열의 총 개수를 구하는 것입니다. 단, R + G + B의 합은 만들 수 있는 문자열의 길이보다 작거나 같아야 합니다.
입력 예시 1
R = 1, G = 1, B = 1, length = 3
출력
주어진 조합으로 만들 수 있는 문자열(R, G, B)의 개수: 6
설명
가능한 문자열은 다음과 같습니다: "RGB", "RBG", "BRG", "BGR", "GRB", "GBR". 즉, RGB의 모든 순열입니다.
입력 예시 2
R = 2, G = 0, B = 2, length = 4
출력
주어진 조합으로 만들 수 있는 문자열(R, G, B)의 개수: 6
설명
가능한 문자열은 다음과 같습니다: "RRBB", "BBRR", "RBRB", "BRBR", "RBBR", "BRRB".
풀이 접근 방법
이 접근 방식에서는 먼저 R, G, B를 각각 요구되는 최소 횟수만큼 배치합니다. 그런 다음 남은 길이, 즉 size − (R + G + B)만큼의 글자를 R, G, B에 분배하는 모든 경우의 수를 계산하여 결과에 더합니다.
정수 값 R, G, B를 입력받습니다.
size는 만들고자 하는 문자열의 길이입니다.
combination(int R, int G, int B, int size) 함수는 모든 입력값을 받아 주어진 조합으로 만들 수 있는 문자열의 개수를 반환합니다.
count를 0으로 초기화합니다.
남은 글자 수를 temp = size − (R + G + B)로 설정합니다.
순열(팩토리얼) 값을 저장하기 위해 크기 size+1인 배열 arr을 선언합니다.
처음에 arr[i]에는 i의 팩토리얼을 저장합니다. i=0부터 i=size까지 반복하면서 arr[i] = arr[i−1] * i로 설정합니다.
조합을 계산하기 위해 두 개의 for 루프를 사용하여 arr[]를 다시 순회합니다.
i는 0부터 temp까지, j는 0부터 temp−i까지 반복하며 temp_2 = temp − (i + j)를 계산합니다.
temp_3 = arr[i + R] * arr[j + B] * arr[temp_2 + G]로 설정합니다.
count += arr[size] / temp_3을 누적합니다.
모든 for 루프가 끝나면 count에 가능한 문자열의 총 개수가 저장됩니다.
count를 결과로 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int combination(int R, int G, int B, int size){
int count = 0;
int temp = size − (R + G + B);
int arr[size+1];
arr[0] = 1;
for (int i = 1; i <= size; i++){
arr[i] = arr[i − 1] * i;
}
for (int i = 0; i <= temp; i++){
for (int j = 0; j <= temp−i; j++){
int temp_2 = temp − (i + j);
int temp_3 = arr[i + R] * arr[j + B] * arr[temp_2 + G];
count += arr[size] / temp_3;
}
}
return count;
}
int main(){
int R = 2, G = 1, B = 1;
int size = 4;
cout<<"Count of number of strings (made of R, G and B) using given combination are: "
<<combination(R, G, B, size);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of number of strings (made of R, G and B) using given combination are: 12