BAEKJOON 11047 : 동전 0 for C

11047번: 동전 0

 입력받은 동전들의 가치로 입력받은 금액을 만드는 동전 개수에서 가장 개수가 적은 값을 출력하는 문제입니다.

 문제의 알고리즘 분류를 보면 <그리디 알고리즘>과 <동전 교환>이 들어가 있습니다. 문제 해결에 앞서 그리디 알고리즘에 대해 알아봅니다.

---

그리디 알고리즘

그리디 알고리즘을 간단히 설명하면 현재 상황에서 가장 최선의 값을 선택하는 알고리즘으로 아래와 같은 상황에서 A 루트를 선택하는 경우입니다.

빨간색의 A 루트, 최단거리 B(파란색) 루트

 전체를 보았을 때 B 루트가 최선이지만, S에서 시작할 때 가장 낮은 값이 3(A 루트)이므로 현재 상황에서 최선의 값을 선택하는 그리디 알고리즘에 방식에 의해 A 루트가 반환이 됩니다.

 이제 코드를 작성해봅니다.

---

코드 작성하기

 먼저 입력으로 동전의 개수와 계산할 금액이 입력됩니다. 따라서 이 값을 받아오는 루틴을 처리합니다.

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

int main(void){
     int n, k;
     scanf("%d %d", &n, &k);
     

 여기에 동전의 개수는 직접 입력받으므로 메모리 동적 할당을 진행합니다. 이번 문제의 경우에는 N의 최댓값은 크지 않으므로 정적 배열을 만들어도 됩니다.

 그러고 나서 N번만큼 반복문을 작성하여 동전의 가치를 받습니다.

    int *coin;
    coin = (int *)malloc(sizeof(int) * n);
    
    for(int i = 0; i < n; ++i){
    	scanf("%d", coin + i);
        // &coin[i] 와 동일한 표현입니다.
    }

 이제 연산을 들어갑니다. 저는 처음 작성할 때는 재귀 함수를 이용해봤습니다.

int gridy(int k, int* coin, int depth){
    int (depth < 0 || !k) return 0;
    int result = k / coin[depth];
    return result + gridy(k % coin[depth], coin, depth - 1);
}

 그런데 이렇게 만들고 보니 굳이 재귀 함수를 이용하지 않아도 되겠더군요. 일단은 재귀 함수로 시작했으니 재귀 함수로 끝을 봅시다. 그런데 이 재귀 함수면 문제가 다 해결되었습니다.

 main()에서 이 함수를 호출해주기만 하면 됩니다.

    printf("%d\n", gridy(k, coin, n-1));
    free(coin); // 동적 할당을 했으니 해제해주는 센스!
    
    return 0;
}

---

완성된 코드

 이렇게 해서 만들어진 코드는 아래와 같습니다.

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

int gridy(int k, int*coin, int depth){
	if(depth < 0 || !k) return 0;
	int result = k / coin[depth];
	return result + gridy(k % coin[depth], coin, depth-1);
}

int main(void){
	int n,k;
	int *coin;
	scanf("%d %d", &n, &k);
	coin = (int *)malloc(sizeof(int) * n);
	for(int i = 0 ; i < n; ++i)
		scanf("%d", coin + i);
	
	printf("%d\n", gridy(k, coin, n-1));
	free(coin);
	return 0;
}

---

번외. 반복문으로 풀기

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

int main(void){
	int n,k;
	int *coin;
	scanf("%d %d", &n, &k);
	coin = (int *)malloc(sizeof(int) * n);
	for(int i = 0 ; i < n; ++i)
		scanf("%d", coin + i);
	
	int result = 0;
	
	for(int i = n-1; 0 <= i; --i){
		result += k / coin[i];
		k %= coin[i];
	}
	
	printf("%d\n", result);
	
	free(coin);
	return 0;
}

 두 번째 존재하는 반복문이 바로 위에서 재귀함수 기능을 하던 부분입니다.