[C언어] 백준 11047 : 동전 0

생각의 흐름

그리디 알고리즘이란 현재 상황에서 최선의 선택을 하는것이라고 한다.
예를 들어, 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

가장 큰 수를 선택하려면, 6 - 128이 맞지만, 그리디에선 17과 6 중에서 17을 고르고 23과 4 중에서 23을 고르기에 17 - 23을 고른다는 것이다.

문제를 보고, 가장 적은 동전의 수를 구해야하기에 그리디를 사용해야하는구나 싶었다.
먼저, 무한루프를 돌려야겠다고 생각했고, break로 탈출조건을 생각했다.
그리고 동전을 입력받으면 저장하는 공간으로 배열을 선언시켜주고, 배열에서 하나씩 감소해가며 큰것부터 차례로 비교하면 되겠구나 싶었다.
마구잡이로 동전을 입력받으면 qsort를 써야되겠구나 싶었는데 애초에 받을 때 오름차순으로 받아 정렬을 할 필요가 없었다.
동전의 갯수를 알아야하기때문에 count를 설정해주었고, 이정도만 생각하고 코드를 작성했다.

내가 푼 코드

#include <stdio.h>

int main()
{
	int n, k, i, t;
	int arr[11];
	int count = 0;
	scanf("%d %d", &n, &k);
	i = 0;
	while (i < n)
	{
		scanf("%d", &arr[i]);
		i++;
	}
	i--; // 이거 안하면 i = n이기에 1 빼줌
	while (1)
	{
		if (k / arr[i] > 0)
		{
			t = k / arr[i];
			count = count + t;
			k = k % arr[i];
		}
		else
			i--;
		if (k == 0)
			break;
	}
	printf("%d", count);
}

다른사람 코드도 비슷하다.