[C] 백준 - 11047번: 동전 0

3월 27일(월) - 그리디 알고리즘(11047번)

11047번: 동전 0

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 주어진 K값을, 오름차순으로 입력되는 가치중에서 가장 큰 값부터 비교해야하므로 그리디 알고리즘 활용

- N과 K 그리고 동전들의 값들을 배열인 value[10]으로 입력받는다

- 오름차순으로 동전의 값들이 입력되었으므로, 가장 큰 값인 value[ N - 1 ] 값부터 K와 비교하며 빼준다

- 만약 K가 value[i]보다 크거나 같으면, K에서 value[i] 값을 빼주며 count++을 해준다

  하지만 K가 value[ i ]보다 작으면 i--를 해주며 더 작은 동전의 값을 가져온다

- 최종적으로는 count의 값을 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int N, K;
	int value[10] = { 0, };
	scanf("%d %d", &N, &K);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &value[i]);
	}

	int i = N - 1;
	int count = 0;
	while (K)
	{
		if (K >= value[i])
		{
			K = K - value[i];
			count++;
		}
		else
		{
			i--;
		}
	}

	printf("%d", count);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ