![]()
문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 어떤 문제인가? 설탕을 n킬로그램을 배달해야 한다. 설탕은 3kg, 5kg 봉지로만 존재해 이 두 가지 종류의 봉지만 사용하여 배달을 해야 한다. 이때, 배달에 필요한 최소 봉지의 개수를 출력하면 된다. 이 문제는 예전에 그리디 알고리즘을 공부할 때 풀었던 문제이다. 지금은 다이내믹 프로그래밍을 공부 중인데 문제가 있어서 이번엔 dp로 풀어보았다. https://codegarden-farmjun.t..
![]()
문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 금액의 최소 화폐 개수를 세는 문제인 5585번과는 약간 다르다. 5585번은 일단 모든 화폐가 서로 배수이고 약수인 관계이기 때문에 무작정 나눠도 되지만, 이 문제 같은 경우는 설탕을 서로 배수나 약수가 아닌 5kg, 3kg으로 정확히 나눠야 한다. 그리디 알고리즘을 통해 설탕을 가장 적은 개수의 봉지로 배달하려면 3kg보다 5kg으로 나누어 떨어지는 것이 좋다. 따라서, 입력받은 설탕의 무게가 ..
