[C언어] 금액 맞추기 (중복조합 응용)

[문제]

지폐 세 종류 1000, 5000, 10000원이 있고 이 지폐들을 이용해 입력된 금액을 만들 수 있는 방법을 나열하고

가능한 방법의 개수도 출력

 

과제로 했던거

중복조합을 이용한다

int main(void)
{
    int items[] = { 1000, 5000, 10000 };
    int* bucket;
    int money, n;
    scanf("%d", &money);
    n = money / 1000;
    bucket = (int*)malloc(sizeof(int) * n);
    printf("%d ", pick(items, 3, bucket, n, n, money));
}

main함수는 이렇게

bucket의 크기는

가장 작은 단위인 1000원짜리로만 금액을 구성할 때 배열의 크기가 가장 크기 때문에 그에 맞춰서 동적할당

pick 함수에선 방법의 개수를 return해서 main에서 출력해준다

 

pick함수는 재귀를 이용할것이다

bucket에는 중복조합으로 뽑힌 원소들이 저장된다

int pick(int* items, int itemsize, int* bucket, int bucketSize, int k, int money) {
    int i, lastIndex, smallest;
    int sum = 0;
    int count = 0;
 
    lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index
 
    for (i = 0; i <= lastIndex; i++)
        sum += bucket[i];
 
    if (sum == money) {
        for (i = 0; i <= lastIndex; i++)
            printf("%d ", bucket[i]);
        printf("\n");
        return 1;
    }
 
    if (sum > money) // 효율성을 위해!!
        return 0;
 
    if (bucketSize == k)
        smallest = 0;
    else
        smallest = bucket[lastIndex]; // 다음에 넣을 돈
 
    // bucket에 items의 원소들을 넣으면서 재귀 호출...
    // 코드 작성
    for (i = 0; i < itemsize; i++)
        if (smallest == items[i])
            smallest = i;
 
    for (i = smallest; i < itemsize; i++) {
        bucket[lastIndex + 1] = items[i];
        count += pick(items, itemsize, bucket, bucketSize, k - 1, money);
    }
 
    return count;
}

21줄부터 설명:

k는 앞으로 뽑아야할 원소의 개수를 뜻한다

일단 if-else문에서는 bucketSize가 k면 bucket에 아무것도 없다는 뜻이된다

그래서 smallest에 0을 넣는다

k가 아니라면 bucket에 이미 원소가 하나라도 존재한다

이 함수는 bucket에 원소들이 오름차순으로 저장된다는걸 전제로 하기 때문에 이미 들어있는 원소 다음에 오는 원소는 마지막으로 저장된 원소보다 크거나 같아야한다 그래서 마지막으로 저장된 원소가 smallest가 된다

 

smallest에는 최종적으로 bucket[lastIndex]에 들어있는 값이 items에서 어디에 위치하는지 인덱스가 저장되어야한다

그래서 단순하게 for문으로 items를 처음부터 앞서 저장한 smallest와 비교 후 smallest에 인덱스를 저장했다

이 부분을 좀 더 깔끔하고 직관적으로 만들 방법이 없을지 고민해봐야한다...

 

마지막 for문의 i는 items의 인덱스로 쓰일것이다 lastIndex 다음 값에 items[smallest]를 대입한후

재귀로 pick을 부른다 bucket에 하나의 원소를 채워 넣었기 때문에 k는 1개를 빼고 호출한다

 

앞부분으로 돌아가서:

lastIndex 계산법은 패스

 

bucket에 저장된 원소들의 합을 구해서 main에서 입력한 금액을 맞췄는지 확인

sum이 금액과 일치하다면 출력한다

한가지 방법을 찾은 것이기 때문에 return 1을 해주면 count에 1이 추가된다

 

여기서 오류가 발생했는데 효율을 위해 추가한 sum이 money보다 큰 경우 아무생각없이 reutrn;만 써놨더니 계속해서 터무니 없는 숫자가 count에 들어갔다

 

반환값이 int인 함수에서 return만 적으면 똥값이 반환된다는 사실을 몰랐었다

 

저부분을 return 0;으로 수정했다

 

 

실행하면 이렇다

6000 을 입력하면 6000을 만들 수 있는 방법 두가지가 출력되고 개수 2가 출력된다