주제
greedy
아이디어
동전 2 와 같은 문제같지만, 사실 푸는 방법은 전혀 다르다..!
바로 이 조건 때문이다!!
이 문제는 배수라는 조건이 있어서 그리디로 단순하게 풀 수 있다.
소스코드
/*
boj11047.cpp
2021-01-08 정설희
동전 0
*/
#include <bits/stdc++.h>
using namespace std;
int arr[11];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = n; i > 0; i--) {
cnt += k / arr[i];
k %= arr[i];
if (k == 0)
break;
}
cout << cnt;
}배운점
DP vs Greedy
동적 프로그래밍
J 출발하기전 신호등, 교통상황, 대중교통, 가는거리를 모두 알아보고 가는방법
장점 : 결정은 모든 가능성을 고려하여 결정한다. 따라서 동적 프로그래밍의 결과는 항상 최적의 결과를 얻을 수 있다.
단점 : 많은 결정 순서들이 생성된다. 그러므로 동적 프로그래밍을 구현하기 위해서 메모리 공간을 많이 필요하다. 👉 주먹구구방식
그리디 알고리즘
P 일단 출발해서 그때 그때 상황에 따라서 가장 빠른 방법으로 앞으로 나아가는 방법
장점 : 가장 간단한 설계방법이고, 좀더 다양한 문제들에 적용할 수 있다.
단점 : 단계별로 진행되어 각 단계에서는 현재 상태에서 가장 최적이라고 판단되는 결정을 내린다. 이 때 전체적으로 최적인지 여부는 검사하지 않고 현재 상태의 입장에서만 보았을 때 가장 최적이라고 판단되는 결정을 내린다. 즉 그리디 알고리즘은 문제에 따라 최적해를 구할 수 있고, 그렇지 않을 수도 있다.
