[C언어] 세뱃돈 뽑기 프로그램 (중복조합 활용)

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

https://aeeazip.tistory.com/3

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

 

 

 

 

 

 

문제 설명

---

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

문제는 다음과 같다.

Q. 1000, 5000, 10000원 짜리 지폐로 세뱃돈을 주려고 할때 주고 싶은 금액을 입력하면 3가지 지폐들을 이용하여 세뱃돈을 만들 수 있는 방법을 출력하세요. (입력은 1000원 단위)

 

예를 들어

입력 : 6000 ← 6천원

출력 : ① 1000 1000 1000 1000 1000 1000

           ② 5000 1000 / 1000 5000

​

위의 출력 결과를 통해 중복이 가능하고 순서가 없음을 알 수 있기 때문에 중복조합이라는 힌트를 얻을 수 있다.

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

Item (뽑아야 할 것들의 정보)	Bucket (뽑힌 것들의 정보)
1000 5000 10000의 값을 갖는 int 배열 item을 생성	item의 원소를 뽑아 해당 원소의 값 / 인덱스를 저장

 

세뱃돈 알고리즘에서는 알고리즘 반복 횟수(몇 번 뽑을것인지)와 item ​이 굉장히 중요하다.

​

 

 

 

 

세뱃돈 알고리즘 핵심

---

알고리즘 반복횟수(K)

알고리즘 반복횟수는 최대 반복 횟수로 설정해주면된다.(조건이 충족되면 main으로 돌아갈 수 있음)

세뱃돈 뽑기에서는 입력값을 1000원으로만 조합할때 가장 많은 반복이 필요하므로

반복횟수(k) = 입력값/1000 이 된다.

​

 

item 정보

item의 값을 단순히 1000 5000 10000 의 값만 갖게 설정하면 item에서 값을 뽑아 bucket에 담을 때마다

입력값과 bucket에 담긴 원소의 합이 같은지 비교해야 한다. (복잡해보이지만 이렇게 푸는 것이 더 효율적)

그러나 item에 0을 추가하면 반복횟수만큼 반복을 끝내야(k = 0) 입력값과 bucket에 담긴 원소의 합이 같은지 비교하기 때문에 코드 이해가 더 쉽다는 장점이 있다.

​

오늘은 두 가지 방법을 모두 사용할 예정이다. คʕ•ﻌ•ʔค

​

 

bucket 정보

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

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

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

​

 

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

 

 

 

 

 

 

풀이

---

​① int item[3] = {1000, 5000, 10000} 인 경우

 

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

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

	lastIndex = bucketSize - k - 1;

	for (i = 0; i <=lastIndex; i++) // 지금까지 뽑은 금액 총합 구하기
		total += item[bucket[i]];

	if (total == 1000 * bucketSize) { // 입력값(money)=1000*bucketSize
		for (i = 0; i <= lastIndex; i++)
			printf("%d ", item[bucket[i]]);
		printf("\n");
		return; // 무한루프 방지
	}
	else if (total > 1000 * bucketSize) // 이미 입력값보다 크면 더 뽑을 필요 없음
		return;
	
	if (bucketSize == k)
		smallest = 0;
	else
		smallest = bucket[lastIndex];

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

int main(void) {
	int item[3] = { 1000,5000,10000 }; // item 정보
	int money; 
	printf("금액은? : ");
	scanf_s("%d", &money);

	int *bucket = (int*)malloc(sizeof(int)*(money/1000)); // bucket 정보
	pick(item, 3, bucket, money/1000, money/1000); // 중복조합 알고리즘
	return;
}

 

 

 

② int item[4] = {0, 1000, 5000, 10000} 인 경우

 

 

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

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

	lastIndex = bucketSize - k - 1;

	if (k == 0) { // 다 뽑으면 출력
		for (i = 0; i < bucketSize; i++) // 지금까지 뽑은 금액 총합 구하기
			total += item[bucket[i]];

		if (total == 1000 * bucketSize) { // 출력 조건(입력값[money]=1000*bucketSize)
			for (i = 0; i < bucketSize; i++)
				if (item[bucket[i]] != 0) // 0원 출력 X
					printf("%d ", item[bucket[i]]);
			printf("\n");
		}
		return; // 무한루프 방지
	}

	if (bucketSize == k)
		smallest = 0;
	else
		smallest = bucket[lastIndex];

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

int main(void) {
	int item[4] = { 1000,5000,10000,0 }; // item 정보(0 추가)
	int money; 
	printf("금액은? : ");
	scanf_s("%d", &money);

	int* bucket = (int*)malloc(sizeof(int) * (money / 1000)); // bucket 정보
	pick(item, 4, bucket, money / 1000, money / 1000); // 중복조합 알고리즘
	return;
}

​

출력부분은 약간 다르지만 전체적인 중복조합 알고리즘은 같으므로 두 경우 모두 알아두는 것이 좋다.

출력결과는 두 경우 모두 같다.

​

코드 결과

​

오늘의 공부 끝 ^_^v