문제 : 2839번: 설탕 배달 (acmicpc.net)
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
문제 상황은 이렇습니다. 특정 무게의 설탕을 남은 것 없이 정확히 3kg, 5kg의 봉지에 나누어 담고 만약, 그렇지 못하면 -1을 출력하는 것입니다. 이때, 봉지의 수가 가장 적은 최적값을 구하는 문제입니다.
이 문제에 그리디, 동적 프로그래밍의 개념이 들어있다라..
그리디(Greedy) = 탐욕
그리디 알고리즘은 탐욕 알고리즘입니다. 위의 문제에서는 설탕 봉지의 수가 적은 값이 목표였습니다.
- 11kg의 설탕에서 5kg 설탕 봉지 2개에 먼저 담는 것
- 8kg의 설탕에서 5kg 설탕 봉지 1개에 담은 후 3kg 설탕 봉지에 담는 것
- 9kg의 설탕에서 5kg 설탕 봉지 1개에 담은 후 3kg 설탕 봉지 1개를 담는 것
위와 같이 가장 좋은 것을 늘 먼저 선택하는 알고리즘입니다!
그렇다면, 여기서 11kg과 9kg의 설탕은 1kg이 남기 때문에 최적값이 아니라는 것을 쉽게 알 수 있습니다.
이것처럼 그리디 알고리즘은 모든 상황을 만족시키지 못하기 때문에 다른 하나의 방법이 더 필요합니다.
동적 프로그래밍(Dynamic Programming)
바로 동적 프로그래밍입니다. 동적 프로그래밍이란 최적해가 나오지 않았을 때, 이전의 결괏값을 가져와
재활용하는 것입니다!
활용하기에 많은 조건과 원리가 있지만 이 문제에서 본다면, 11kg은 5kg 두 봉지에 담고 1kg이 남는 문제의 상황이 생긴다.
그렇다면 5kg 한 봉지를 덜어내고 3kg 두 봉지로 나누어 담으면 3 봉지에 11kg을 모두 나누어 담을 수 있다.
즉, 문제의 상황이 생겼을 때 이전의 결괏값을 가져와 이전의 방식과는 다른 방식(5kg 봉지말고 3kg 봉지에)으로 접근하는 것입니다.
여기서 생각해볼 것은 동적 프로그래밍과 그리디 알고리즘 각각으로 놓고 본다면 문제의 해결시간이 매우 많이 걸리거나 최적해를 구하지 못할 수도 있습니다..!
위의 문제를 파이썬으로 코드를 짜본 것입니다.