글 읽기 - 동전교환문제 dp or greedy

value가 주어지고 동전 단위 (ex. {1,5,20,25})가 주어질 때, (각 동전의 갯수는 무한)

단위마다 greedy하게 풀 수 있는 것과 아닌 것들이 있는데

혹시 greedy하게 풀 수 있는 특정한 조건이 있나요

{7,6,5,4,3,2,1} 이 동전 집합도 greedy하게 풀 수 있는 것 같은데..

{1,5,20,25}는 안되고 {1,5,10,25}는 되는 것 같네요

보통 큰 쪽이 작은 쪽의 배수 관계에 있다면 greedy로 풀립니다.

작은 쪽 x개 = 큰 거 1개로 covered가 되기 때문이죠.

그렇지 않은 경우에도 greedy로 풀리는 것도 있는데

그런 경우들은 직접 확인해야하나요?

예를 들어

{25, 10, 5, 1}, {7,6,5,4,3,2,1} 의 경우에서 처럼요

직접 확인이라는 게 프로그램이 greedy의 가능 여부를 판단한다는 말인가요? 그렇게 할 일은 아마 거의 없다고 생각합니다. 애초에 greedy가 안 되는 집합이 주어질 수 있는 문제라면 처음부터 dp로 풀 것을 요구하는 거겠죠.

동전의 최대 액면가 *2까지의 모든 금액에 대해 그리디가 된다면, 그 뒤의 모든 금액에 대해서도 그리디가 된다는 property는 있습니다.

icpc.me/13137 문제를 참고해보세요

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge