(백준 11047번 동전 0 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 3탄

24년에도 뚠뚠!🐜 열심히 알고리즘 문제를 풀고자 한다!

 

이전 발행글은 여기에~!

2024.01.01 - [알고리즘] - (백준 13904번 과제 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 2탄

(백준 13904번 과제 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 2

 

헤헤 그리고 나의 공스타그램은 여기에...🤭

https://www.instagram.com/study_human.c/

 

백준 11047번

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

11047번: 동전 0

 

참고로 이 문제는 라이님 블로그에 자세히 설명되어 있다. 

이 문제에서의 핵심은 주어진 동전이 약수, 배수의 관계에 있다는 점이다.

즉, 큰 동전은 작은 동전의 합으로 나타낼 수 있기 때문에 큰 동전을 무조건 많이 사용해야 동전을 최소로 사용할 수 있다는 아이디어를 담고 있다.(←Greedy Algorithm)

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

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 cnt = 0;
	
	for (int i = N - 1; i >= 0; i--) {
		while (1) {
			if (K >= Arr[i]) {
				cnt++;
				K -= Arr[i];
			}
			else break;
		}
		if (K == 0) break;
	}

	printf("%d", cnt);
	delete[]Arr;
}

 

요번건 깔끔하게 십분컷!

 

이번에는 다른 분들이 푸신 숏코딩 풀이를 봤는데, 아래와 같이 입력을 받는게 신기했다.

이렇게 입력을 받으면 좋은 점은 input과 반대방향으로 Arr에 저장할 수 있다는 점이다!

int Arr[10];
while(N--) scanf("%d", Arr+N);

다음에 써 먹어보면 좋을 것 같다👍🏻

모두들 해피뉴이어입니당!