그리디알고리즘

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 금액의 최소 화폐 개수를 세는 문제인 5585번과는 약간 다르다. 5585번은 일단 모든 화폐가 서로 배수이고 약수인 관계이기 때문에 무작정 나눠도 되지만, 이 문제 같은 경우는 설탕을 서로 배수나 약수가 아닌 5kg, 3kg으로 정확히 나눠야 한다. 그리디 알고리즘을 통해 설탕을 가장 적은 개수의 봉지로 배달하려면 3kg보다 5kg으로 나누어 떨어지는 것이 좋다. 따라서, 입력받은 설탕의 무게가 ..

문제 : https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 아주 기초적이고 대표적인 그리디 알고리즘의 예시 #include using namespace std; int coin[] = {500, 100 ,50, 10, 5, 1}; int main(){ int money; cin >> money; int realMoney = 1000 - money; int cnt=0; for(int i=0; i

문제 : https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프들이 병렬로 연결되어 무게를 들 때 로프들 중 가장 작은 무게를 들 수 있는 로프가 들 수 있는 무게가 병렬로 연결된 로프들이 각각 들어야 할 무게가 되는 것이 핵심이다. 1. 로프들이 들 수 있는 무게의 정보를 저장할 벡터 rope를 선언하고 문제의 요구에 맞게 입력을 받는다. 2. rope를 sort함수를 사용해 내림차순으로 정렬해준다. 3. 병렬로 연결된 로프들이 들어 ..