COINS 문제가 계속 시간초과에요!!

  • gkwhdgns
    gkwhdgns

    COINS문제를 풀고 있습니다.

    다음과 같은 과정으로 문제를 풀었는데요,

    • 동적 할당하여 배열에 동전 값을 입력
    • 입력받은 동전을 큰 순서부터 내림차순으로 정렬 (이 때, 계산하고자 하는 금액보다 큰 금액은 제거하여 정렬)
    • 큰 동전부터 0개 ~ 셀 수 있는 가장 큰 경우까지 반복
    • 각각의 경우에서 재귀함수를 호출해 더 작은 동전의 경우를 계산
    • 가장 작은 동전의 경우에서는 count값 추가.
    • MAX 보다 작은 나머지를 반환

    하는 재귀 알고리즘을 사용하였습니다.
    그런데 계속하여 마지막 경우 (총액이 1278) 에서 계산 시간이 엄청 길어지네요. 물론 시간 초과로 오답이 나왔습니다.

    어떻게 하면 시간을 단축하여 개선할 수 있을까요?

    고수님들의 도움 부탁드립니다.

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

#define MAX 1000000007

int check2(int amount, int coins[], int idx, int size){

    unsigned int count = 0;
    int val = amount/coins[idx];

    for(int i=0; i<=val; i++){
        if(size-1 != idx){
            count += check2(amount-i*coins[idx], coins, idx+1, size);
        }else{
            return ++count;         
        }
    }
    return count%MAX;
}

int* sort(int* arr, int* size, int amount){

    for(int i=0; i<*size; i++){
        for(int j=i+1; j<*size; j++){
            if(arr[i]<arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    // 총 금액보다 큰 단위의 동전 제거
    while(arr[0] > amount){
        arr = &arr[1];
        *size = *size -1;
    }

    return arr;
}

int main(){

    int T = 0;
    scanf("%d", &T);

    for(int i=0;i<T;i++){

        int M, C, count = 0;
        scanf("%d %d", &M, &C);

        int* coins = (int*)malloc(sizeof(int) * C);

        for(int j=0; j< C; j++){
            scanf("%d", &coins[j]);
        }

        coins = sort(coins, &C, M);

        count = check2(M, coins, 0, C);

        printf("%d\n", count);

        coins = NULL;
        free(coins);
    }

    return 0;
}

    8년 전
1개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan


    완전 탐색이 아닌, 동적계획법을 이용하여 문제를 해결해보세요.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.