1398번

1398번 - 동전

동전을 최소개수로 사용하는 방법을 찾는 문제.

그리디 문제에서 많이 나오지만, 만약 동전이 배수를 이루지 않는다면, 그리디 방식으로 풀 수 없다.

그래서 동전을 써가면서 규칙을 찾아봤다.

일단 가장 큰 가치를 가지는 동전을 써야한다는 기본 베이스는 똑같이 시작했다.

25 * 100^k , 100이라는 값에 주목했다. 이는, 숫자의 길이가 짝수 일 때 사용해야 이익을 볼 수 있다는 생각을 떠올렸다.

만약 125원을 만들려면, 100원1개,10원2개,1원5개 or 25원 5개 or 100원1개,25원1개..

결국 25 * 100^k 은 짝수일 때 사용할 수 밖에 없다, 홀수 길이일 때 사용하면 오히려 손해가 발생한다.

그래서 10^k 로 모두 구해보면서 ,짝수일때만 25*100^k 의 동전을 사용하는 완전 탐색을 구현했다.

항상 최소값을 구하는 문제는

  if (sum > ans)

    {

        return;

    }

이 구문을 넣으면 속도가 빨라진다.

또한 처음에는 25*100^k 동전을 먼저 사용하고, 10^k 를 사용하는 방식으로 풀었더니 시간 초과가 발생했다.

하지만 위의 구문을 이용하기 위해 10^k 를 먼저 사용하도록 했더니 속도가 훨씬 향상됐다.

<정답 코드>

#include<iostream>
#include<math.h>
using namespace std;
long long ans;
int getlen(long long num)
{
    int len = 0;
    while (num > 0)
    {
        num /= 10;
        len++;
    }
 
    return len;
}
void go(long long cost,long long sum)
{
 
    if (sum > ans)
    {
        return;
    }
 
    if (cost < 0)
    {
        return;
    }
    
    if (cost == 0)
    {
        ans = sum < ans ? sum : ans;
        return;
    }
 
 
    int len = getlen(cost);
    long long mod1 = pow(10, len - 1);
    long long mod2 = pow(10, len - 2);
 
    go(cost - (cost / mod1)*mod1, sum + (cost / mod1));
 
    if (len % 2 == 0)
    {
        go(cost - 25 * mod2, sum + 1);
    }
}
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        long long cost;
        ans = 987654321;
        scanf("%lld", &cost);
 
        go(cost,0);
        
        printf("%lld\n", ans);
    }
    return 0;
}