[4주차] 백준 11047번: 동전 0_C언어

백준 11047: 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

- 준규가 가진 동전의 종류의 개수(N)와 동전이 만들어야 할 금액(K)를 입력받는다. 

- 동전의 종류를 입력받는다. (오름차순)

- K원을 만드는데 필요한 동전 개수의 최솟값이 출력된다.

---

#include <stdio.h>

int main()
{
	int N, K;
	int coin[10];
	int a;
	int result = 0;

	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &coin[i]);
	}
	
	
	for (int i = N - 1; i >= 0; i--) {
		a = K / coin[i];
		if (a > 0) {
			K -= coin[i] * a;
			result += a;
		}

	}

	printf("%d", result);
}

- 준규가 가진 동전의 종류의 개수(N)와 동전이 만들어야 할 금액(K)를 입력받는다.

- 동전의 종류가 최대 10개이므로 크기가 10인 coin 배열을 선언하고 이 배열에 동전들을 오름차순으로 입력받는다. 

- 큰 금액의 동전부터 순서대로 K에 나눠주고 그 값이 0보다 크면 그 값*금액 만큼을 K에서 빼준다.

-> ex. 4790원

-> 5000원 이상의 동전은 나눗셈의 결과가 0보다 작으므로 통과한다. 

-> 4700/1000 = 4 => (4790 - 4*1000 = 790)

-> 790/100 = 7 => (790 - 7*100 = 900)

-> 90/10 = 9 => (90 - 10*9 = 0)

---

나는 아무 생각없이 문제를 풀었는데 이 문제가 그리디 알고리즘 문제라고 한다..

그리디 알고리즘이 뭔지 몰라서 찾아보았다.

---

[출처]: https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98​

그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는데, 리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택하는 방식이다. 
(이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.)

물론 모든 경우에서 그리디 알고리즘이 통하지는 않는다. 

예를 들어, 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로를 1개밖에 받지 못한다. 지금 당장 최선의 선택은 마시멜로 1개를 받는 거지만, 결과적으로는 1분 기다렸다가 2개 받는 게 최선이기 때문이다. 

 

그러나 그리디 알고리즘이 통하는 문제들도 많다. 대표적으로 거스름돈 문제가 있다.

예를들어, 거스름돈을 최소한의 동전 개수로 계산해야 할 때 가장 최선의 방법은 가장 큰 단위의 돈부터 생각하자는 것인데, 이때는 그리디 알고리즘이 전체 알고리즘에서도 최선의 해결방법이 된다.

 

- 그리디 알고리즘의 조건

-> (탐욕스러운 선택 조건) 탐욕적인 선택은 항상 안전해야 한다.

// '안전하다'라는 것은 이 선택으로 인해 전체 문제의 가장 알맞는 해결방법을 반드시 도출할 수 있어야 한다는 뜻이다.

// 그리디 알고리즘을 사용하면 항상 최적해가 나오는 것이 아니기 때문에, 그리디 알고리즘이 적절하게 사용될 수 있는가를 고민해봐야 한다는 뜻인 것 같다. 

-> (최적 부분 구조 조건) 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결방법이어야 한다.

// 전체 구조의 해결 방법이 각 부분에 대해서도 효율적인 해결방법이어야 한다는 것이다.

---

아직 그리디 알고리즘 정확히는 모르겠지만 그래도 문제를 접해보았고,

나만의 방식으로 해결했다는 점이 가장 뿌듯했다.

재밌었다!