[Baekjoon, C++] 11047번 : 동전 0

도입

백준 단계별 풀기 그리디 알고리즘 첫 번째 문제이다.

백준 11047번 문제, 입력, 출력

---

백준 11047번 입출력 예제 1,2

 

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 받는 것은 오름차순으로 받는데 큰 수부터 내림차순으로 푸는 것이 좋다고 판단하였다. 적합성 판단에서 최대한 큰가치의 동전이 연산을 덜 하기 때문이다. 따라서, algorithm의 sort 함수를 사용한다. 오름차순으로 받은 숫자를 벡터에 저장하고, 해당 벡터 변수를 내림차순으로 sort한다.

 

2. 목표 금액(targetAmount)에서 내림차순으로 정렬된 가치 별 동전(valueOfCoin[])을 뺀다. 그리고 0보다 크다면, 최소 동전 수(minAmountOfCoin)의 값을 1 올린다. 그리고 뺀 금액에서 다시 이것을 반복한다.  

---

코드

#include<iostream>  
#include <vector>
#include <algorithm>

using namespace std;

int cmp(int a, int b) { // 내림차순
	return a > b;
}
int main() {
	int kindOfCoin, targetAmount, minAmountOfCoint = 0;
	cin >> kindOfCoin >> targetAmount;
	vector<int> valueOfCoin(kindOfCoin);

	for (int i = 0; i < kindOfCoin; i++) {
		cin >> valueOfCoin[i];
	}
	sort(valueOfCoin.begin(), valueOfCoin.end(), cmp);

	for (int i = 0; i < kindOfCoin; i++) {
		while (targetAmount - valueOfCoin[i] >= 0) {
			minAmountOfCoint++;
			targetAmount -= valueOfCoin[i];
		}
	}
	cout << minAmountOfCoint << '\n';
}
 

---

마무리

이상으로 그리디 알고리즘 동전 문제를 마치겠다.

 

 

출처 ->

m.blog.naver.com/PostView.nhn?blogId=dilector&logNo=220841254412&proxyReferer=https:%2F%2Fwww.google.com%2F

blog.skby.net/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/