[C언어] 연기상 뽑기 프로그램 (순열 활용)

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

https://aeeazip.tistory.com/4

[C언어] 순열과 중복순열

​

 

 

 

 

 

문제 설명

---

​이번 글에서는 순열을 활용한 연기상(수상자) 뽑기 프로그램을 작성해 볼 예정이다.

문제는 다음과 같다.

Q. 배우들 중에서 n명을 뽑아서 최우수연기상, 우수연기상을 주려 한다. 1명은 단 하나의 상만 받을 수 있다. 배우를 정진영, 신동우, 이정환, 차선우, 공찬식 중에서 선택한다고 할때 가능한 경우의 수를 출력해보자.

1명은 단 하나의 상만 받을 수 있다는 점에서 중복이 불가능함을 알 수 있고 상의 종류가 다르기 때문에 순서가 있음을 알 수 있기 때문에 순열이라는 힌트를 얻을 수 있다.

​

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

Item (뽑아야 할 것들의 정보)	Bucket (뽑힌 것들의 정보)
정진영/ 신동우/ 이정환/ 차선우/ 공찬식 등 배우 정보가 담긴 char 배열 item을 생성	item의 원소를 뽑아 해당 원소의 값 / 인덱스를 저장

​

 

 

 

 

 

bucket 정보

---

bucket의 0번째 인덱스에 item의 '정진영' 이라는 값 정보를 담는다고 할 때

① 값을 직접 넣는다면 bucket[0] = '정진영' 이 가능

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

​

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

​

 

 

 

 

 

풀이

---

​

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

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

	lastIndex = bucketSize - k - 1; 

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

	smallest = 0;

	for (i = smallest; i < itemSize; i++) {
		flag = 0;
		for (j = 0; j <= lastIndex; j++) { // 순열 알고리즘의 핵심
			if (bucket[j] == i) {
				flag = 1;
				break;
			}
		}

		if (!flag) { 
			bucket[lastIndex + 1] = i;
			pick(item, itemSize, bucket, bucketSize, k - 1);
		}
	}
	return;
}

int main(void) {
	char item[5][7] = { "정진영", "신동우", "이정환", "차선우", "공찬식" }; // item 정보
	int n, i;
	printf("상의 종류는? ");
	scanf_s("%d", &n);

	int* bucket = (int*)malloc(sizeof(int) * n); // bucket 정보

	for (i = 0; i < n; i++)
		printf("\t상%d", (i + 1));
	printf("\n");

	pick(item, 5, bucket, n, n); // 순열 알고리즘
	return;
}

 

​

코드 결과

 

오늘의 공부 끝 ^_^v