init 5주차 과제 - 그리디

1. 과제

백준 그리디 알고리즘 11047번 문제

• 문제
• 내가 푼 코드

2. 참고한 사항 / 중요 사항

이 문제를 그리디 알고리즘으로 해결할 수 있는 이유

사용할 수 있는 가장 큰 값의 동전을 먼저 사용하면 단위가 작은 동전들의 수를 최소화할 수 있는 점을 포인트로 잡고 가야 한다. 동전 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

하지만 위와 같이 단위가 배수가 되지 않는다면, 그리디 알고리즘으로 최적해를 얻을 수 없게 된다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

나는 이 문제를 풀기 위해 각 단위들을 배열에 담고, 각 배열에서 반복문을 진행하면서 큰 단위부터 K원을 나누면서 동전의 개수를 구하는 식으로 그리디 알고리즘을 구현하였다.

3. 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	
	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

	int count = 0;
	for (int i = N - 1; i >= 0; i--) {
		count += K / arr[i];
		K = K % arr[i];
	}
	printf("%d", count);
	return 0;
}

4. 제출 화면