중복 조합

고등학교 확률과 통계라는 과목에서 중복조합에 대한 내용을 공부한적이 있다.

그 중 중복조합과 관련된 문제 중 가장 일반적인 문제가 

a + b + c = 6 일 때 음이 아닌 정수 의 (a, b, c) 쌍이 몇개 인지 구하는 것이다.

 

이 문제를 중복 조합 공식으로 풀면 그 개수만 알 뿐 어떤 조합이 생기는지는 알 수 없다.

그래서 이를 코드로 작성하면 아래와 같다.

static void comb()
{
	for (int a = 0; a <= 6; a++)
	{
		for (int b = 0; b <= 6; b++)
		{
			for (int c = 0; c <= 6; c++)
			{
				if (a + b + c == 6)
				{
					printf("%d %d %d\n", a, b, c);
				}
			}
		}
	}
}

단순히 반복문을 중첩해서 구하는 것이다.

 

여기서 a + 2b + c = 6 과 같은 식은 b에 대한 조건을 추가하여 구할 수 있다.

2b <= 6 이므로, b <= 3 여야만 한다. 따라서 아래와 같이 작성하면 된다.

static void comb()
{
	for (int a = 0; a <= 6; a++)
	{
		for (int b = 0; b <= 6 / 2; b++)
		{
			for (int c = 0; c <= 6; c++)
			{
				if (a + 2 * b + c == 6)
				{
					printf("%d %d %d\n", a, b, c);
				}
			}
		}
	}
}

이렇게 하면 중복 조합의 모든 경우를 볼 수 있다. 그러나 입력에 따라 유연하게 동작하지 않기 때문에, 어떤 조합의 결과를 보고 싶을 때 마다 코드를 수정해야 한다. 

그래서 재귀를 이용하여 아래와 같이 작성 할 수 있다.

static int N, K;
static int v_list[10];

static void comb(int cnt, int v)
{
	if (v == K)
	{
		for (int i = 1; i < cnt; i++)
			printf("%d ", v_list[i]);
		puts("");
		return;
	}
	if (cnt > N)
		return;

	for (int i = 0; i <= K; i++)
	{
		int val = v + i;
		v_list[cnt] = i;
		comb(cnt + 1, val);
	}
}

int main()
{
	N = 3; K = 6;
	comb(1, 0);
}

N은 순서쌍을 이루는 정수의 개수, K는 원하는 값을 말한다.

재귀의 탈출 조건은 크게 누적된 값이 K가 되는 경우와, cnt > N 일 때이다.

이에 대해서 a + b + c = 6 을 예로 들어보겠다.

 

먼저 a는 0이 선택되고 이는 v_list[1] = 0 이다.

이제 b를 선택할 차례이고 마찬가지로 0을 선택한다. v_list[1 + 1] = v_list[2] = 0 이다.

현재 2개의 값이 선택 된 것이다.

이제 c를 선택할 차례이다. 역시 0을 선택하고 v_list[2 + 1] = v_list[3] = 0 이다.

그리고 재귀 호출 을 하게 되면 cnt 는 4가 된다. 즉 더 이상 선택 할 수 없음을 말하는 것이다.

이제 c가 6이 선택된다. v_list[3] = 6 이고 val = (0 + 0) + 6 = 6 이다.

다시 재귀 호출 되면 v == 6 == K 이므로 기록된 값 들을 cnt 만큼 만 출력하는 것이다.

 

이제 이 코드를 다시 응용 해서 a + 2b + c = 6 과 같은 조합 문제도 풀 수 있다.

static int N, K;
static int v_list[10];
static int equation[10];

static void comb(int cnt, int v)
{
	if (v == K)
	{
		for (int i = 1; i < cnt; i++)
			printf("%d ", v_list[i]);
		puts("");
		return;
	}
	if (cnt > N)
		return;

	for (int i = 0; i <= K / equation[cnt]; i++)
	{
		int val = v + i * equation[cnt];
		v_list[cnt] = i;
		comb(cnt + 1, val);
	}
}

int main()
{
	N = 3; K = 6;
	equation[1] = 1; equation[2] = 2; equation[3] = 1;
	comb(1, 0);
}

equation 이라는 배열의 각 값은 해당 위치에 계수를 의미한다.