큰 단위의 동전이 그보다 한 단계 작은 단위의 동전의 배수 단위이면 큰 단위부터 주는 게 최적해 보장된다는데,
1 5 10 25 50도 최적해 보장되던데...
(근데 25는 10의 배수가 아님. 5의 배수이긴 하지만)
1 5 10 12 25 50은 안되고...
꼭 한 단계 작은 게 아니라 1보다 큰 임의의 작은 단위의 동전의 배수이기만 하면 되는거 아님?
1 5 10 25 50도 최적해 보장되던데...
(근데 25는 10의 배수가 아님. 5의 배수이긴 하지만)
1 5 10 12 25 50은 안되고...
꼭 한 단계 작은 게 아니라 1보다 큰 임의의 작은 단위의 동전의 배수이기만 하면 되는거 아님?
큰 단위의 동전이 그보다 한 단계 작은 단위의 동전의 배수이면 그리디 최적해 보장 >> 항상 사실임 그리디 최적해 보장이면 큰 단위의 동전이 그보다 한 단계 작은 동전의 배수 >> 항상 사실은 아님
a이면 b이다 == b이면 a이다 가 항상 성립하는 게 아님
아례 예시에서 15원 만들때 12원 집어넣을거임? - dc App
ㄴㄴ
https://www.sciencedirect.com/science/article/abs/pii/S0167637704000823
그리디가 통하는지 검사해주는 알고리즘이 있다는 모양인데요
최적해 보장하는 동전 간위 조건이랄게 딱 떨어지지 않나보네
단위
https://www.acmicpc.net/problem/13137