[Leetcode] 322. Coin Change

Identifying the Problem

amount를 지불하는 최소한의 coin 개수를 구한다.

단 coins로 amount를 만들지 못할 경우 -1을 리턴한다.

Organizing thoughts

coins = [1,2,5] amount = 11인 경우

5개를 최대한 (2개)내고 , 나머지를 1로 (1개) 내는 방법이 있다.

11/5 + 1/2 + 1/1 = 3

 

하지만 coins = [2,3,6,7] amount = 12 인 경우

12/7 + 5/6 + 5/3 + 2/2 = 3개이지만,

6+6 = 12 으로 생각하면, 2개로 더 적은 coin이 사용된다.

 

따라서, amount에서 coin별로 값을 뱃을 때, 그 값이 필요한 동전의 개수를 파악하며 

조심스럽게 접근해야 한다.

 

즉 1 부터 amount까지의 개별로 필요한 coin의 수를 파악해야 한다.

11에서 5를 뺀 값 6을 최소한의 코인으로 얼마나 만들 수 있는지

6에서 5를 뺀 값 1을 최소한의 코인으로 얼마나 만들 수 있는지

그리고, 여기서 DP의 패턴을 발견 할 수 있다.

 

Sourcecode 

int cmp(const void *p1, const void *p2)
{
    return *(int *)p1 - *(int *)p2;
}

int find_min(int a , int b);

int coinChange(int* coins, int coinsSize, int amount)
{
  
	qsort(coins, coinsSize, sizeof(int), cmp); //coin 오름차순 정렬
    //coinSize인 이유 : coinsSize/sizeof(int)는 coinsSize가 배열인 경우 배열의 길이를 구하는 용도
    
    int* count = malloc(sizeof(int)  * (amount+1)); //0~amount까지의 count가 들어갈 배열
    
    int flag = 0; //주어진 코인으로 해당 수를 만들 수 있는지 판단하는 flag
    int min; 
    //12에서 7을 뺀 경우보다 6을 뺀 경우의 수가 더 적은 코인을 가져오기에
    //각 경우를 비교하기위해 min을 사용
    
    if(amount == 0) return 0; //아무것도 없는 경우 0리턴
    
    count[0] = 0; //초기 설정 0은 어차피 0개고
    count[1] = coins[0] == 1 ? 1 : -1; //1은 1이 있으면 1 없으면 -1로 유추 가능

    
    for(int i = 2; i<= amount; i++)
    {    for(int k = coinsSize-1; k>=0; k--) //큰 코인부터 줄여나감
        {
            int t = i - coins[k];
            
            if(t >= 0 && count[t] != -1 )
            {
                if(flag == 0) min = count[t]; 
                //min의 최소는 맨 처음 코인으로 가능한 경우 수
                
                min = find_min(min,count[t]);
                count[i] = min + 1; //최소한의 코인 개수 + coin[k] 이므로 + 1 
                flag = 1; //주어진 코인으로 i를 제작할 수 있으니 flag 세움
            }
            else if (flag == 0) // flag
               count[i] = -1;
            
       
        }
        
        flag = 0; //flag 0으로 되돌려줌
       
     }
    
    return count[amount]; //마지막 count를 구한다.
}

int find_min(int a , int b) //min 함수
{
    if(a<b) return a;
    else return b;
}