[C언어] 공뽑기 프로그램 (조합 활용)

저번 글에서 조합 알고리즘에 대한 개념과 간단한 예제를 살펴보았다.

https://aeeazip.tistory.com/3

[C언어] 조합과 중복조합

 

 

 

 

 

문제 설명

---

이번 글에서는 조합을 활용한 공뽑기 프로그램을 작성해 볼 예정이다.

문제는 다음과 같다.

Q. ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’의 번호가 매겨져 있는 공 7개 중에서 3개를 뽑아 출력하세요. (중복허용X)

 

문제에서 7개 중 3개를 뽑는다고 표현했고 중복을 허용하지 않기 때문에 조합이라는 힌트를 얻을 수 있다.

그렇다면 item과 bucket엔 무엇이 담겨야 할까? (item = 뽑아야 할 것들의 정보 / bucket = 뽑힌 것들의 정보)

​

Item (뽑아야 할 것들의 정보)	Bucket (뽑힌 것들의 정보)
A~G 값을 갖는 char형 배열 item을 생성 ex. char item[7] = {'A', 'B', ··· , 'G'};	item의 원소를 뽑아 해당 원소의 값 / 인덱스를 저장

→ bucket의 0번째 인덱스에 item의 A라는 값 정보를 담는다고 할 때

① 값을 직접 넣는다면 bucket[0] = 'A' 가 가능

② 인덱스를 선택한다면 item 배열에서 A의 인덱스인 0이 선택되어 bucket[0] = 0 이 가능

​

이 글에서는 bucket에 item 정보의 인덱스를 저장하는 두 번째 방법을 사용할 것이다.

 

 

 

 

 

풀이

---

​

#include <stdio.h>
#include <stdlib.h>

/*
    n = item 정보
    bucket = 뽑은 item의 정보를 담을 배열
    bucketSize = bucket에 대한 정보(배열의 크기)
    k = 앞으로 뽑아야 할 개수
*/
void pick(char *item, int itemSize, int *bucket, int bucketSize, int k) {
	int i, lastIndex, smallest;

	if (k == 0) { // 다 뽑으면 출력하기
		for (i = 0; i < bucketSize; i++)
			printf("%c ", item[bucket[i]]);
		printf("\n");
		return; // 무한루프 방지
	}

	lastIndex = bucketSize - k - 1;
	if (bucketSize == k)
		smallest = 0;
	else
		smallest = bucket[lastIndex] + 1; // 가장 마지막에 뽑힌 수보다 큰 수를 뽑는다

	for (i = smallest; i < itemSize; i++) {
		bucket[lastIndex + 1] = i;
		pick(item, itemSize, bucket, bucketSize, k - 1); // k-1 = 앞으로 뽑아야 할 개수를 하나 감소

	}
	return;
}

int main(void) {
	char item[7] = { 'A','B','C','D', 'E', 'F','G' }; // item(공) 정보 
	int bucket[3]; // bucket 정보

	pick(item, 7, bucket, 3, 3); // 조합 알고리즘
	return;
}

 

코드 결과

 

- 7C3 = 이므로 총 35가지 경우의 수를 만족하고 모든 경우의 수가 올바르게 출력된 걸 확인할 수 있다

​

오늘의 공부 끝 ^_^v