문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이 문제는 이중 반복문(3의 배수 + 5의 배수의 합)으로 해결할 수도 있지만, 효율적인 풀이를 위해 그리디 알고리즘과 DP를 이용할 수 있다. - 그리디 풀이 1. N이 5의 배수라면 답은 N/5 2. N이 5의 배수가 아니라면 3kg 에 한 번 담고(cnt++, N -= 3) 다시 반복문을 실행한다. 3. N이 0보다 작아지면 답은 -1 - dp 풀이 N이라는 숫자를 만들기 위해서 (N - 3) + 3 또는 (N - 5) + 5 의 경우로 나눠 볼 수 있다...