2839번: 설탕 배달 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제를 다시 정리해보면 다음과 같다. 사탕가게에 설탕을 정확히 N kg을 배달한다. N은 3이상 5,000이하의 자연수 봉지는 3kg, 5kg 두 가지가 있고, 최대한 적은 봉지로 가져가려고 한다. 몇 봉지를 가져가야할까? 이에 대한 아이디어는 두 가지를 떠올릴 수 있었다. 첫번째는 그리디 방식으로 푸는 것이다. 3보다 5로 나누었을 때, 봉지 개수를 줄일 수 있기 때문에, N이 5로 나누어질 때까지, 3을 계속 빼자 두번째는 DP를 생각했다. dp..
