C언어 백준 알고리즘 11047번 (동전0)

이 문제는 그리디 알고리즘을 사용해서 푸는 문제이다.

그리디 알고리즘이란 

그리디 알고리즘의 정의

선택의 순간마다 바로 눈 앞에 있는 가장 큰 이익, 최적의 상황만을 쫓아가는 탐욕적인 (Greedy) 알고리즘이다.

 개인적으로 그리디 알고리즘의 가장 쉬운 문제라고 생각한다. 

오름차순으로 동전의 가치가 입력되기 때문에 정렬을 해야 할 필요가 없기 때문이다.

 

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

int main(void) {

	int num, money;
	int cnt = 0;
	scanf("%d %d", &num,&money); //테스트 케이스의 개수와 가치 값을 입력받는다.
	
	//printf("%d\n%d", num,  money);
	int* arr;

	arr = (int*)malloc(sizeof(int) * num); // 테스트 케이스의 개수만큼 동적할당 후, 동전의 값을 입력받는다.

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

		scanf("%d", &arr[i]);             //동전의 값을 오름차순으로 입력.

	}
	for (int i = num - 1; i  > -1; i--) {
		
		if (money >= arr[i]) {           //가치 값을 동전 값의 역순(큰 값부터)으로 비교하여, 가치 값이 동전 값보다 크면 루프 진입

			while (money >= arr[i]) {

				money = money - arr[i]; //가치 값이 동전값보다 작아질때까지 빼준다.

				//printf("%d\n", money);

				cnt++;                  //카운트
				
			}
		}
	}
	printf("%d", cnt);					//출력



	return 0;
}

동전의 개수가 10을 넘지 않기 때문에 동적할당을 하지 않아도 되었는데, 나는 저 조건을 똑바로 읽지 않아서 동적할당을 해서 문제를 풀었다. 동전의 가치를 배열에 입력하면 오름차순으로 배열의 원소에 동전의 가치가 들어간다.

그리디 알고리즘은 가장 큰 이익부터(이 문제에서는 가치가 가장 큰 동전)을 좇기 때문에 배열의 역순으로 반복문을 사용하여 돈 값에서 가장 큰 동전의 값부터 뺀다.. 여기서 포인트는 더 이상 뺄 수 없을 때 까지 빼야 한다는 것인데, while문의 조건식을 돈의 값이 동전의 값보다 같거나 클 때 ( 돈 값에서 동전의 값을 뺄 수 있다.)로 설정해서 조건을 만족하지 못 할 때까지 계속 빼는 것이다. 그리고 뺄 때 마다 카운트를 증가시켜서 카운트의 개수를 출력한다.