[백준][C++] 11047 동전 0

11047. 동전 0

11047번: 동전 0

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

처음 이 문제를 봤을 땐...

이 예제를 보고 "그냥 큰 거 나누고... 작은 거 나누면 되는 거 아니야?" 하는 안일한 생각을 잠시 동안 했다가

 

2 19 3 7이라던가... 2 9 3 7 등의 예외가 있는 예제가 머리를 스쳐 지나가서 생각을 고쳐먹었다.

 

섣불리 사용할 수 있는 동전을 사용했다가, 다음 동전들이 나누어지지 못해 K를 만들지 못하는 불상사가 생길 수 있으므로...

 

내가 생각한 방법은 사용할 수 있는 동전 - 1까지만 사용을 하고, 다음 동전들을 검사해서 사용하지 않았던 하나의 동전을 사용할지, 말지의 여부를 계속 결정하는 것이다.

 

알고리즘 설계

1. 사용할 수 있는 동전 - 1을 사용한다.

• 목표 금액인 K에서 방금 사용한 동전 금액을 차감해준다

2. 만약 위에서 모든 동전을 사용했더라면, 위에 사용한 동전보다 작은 동전들이 남은 K로 나누어 떨어지는지 검사한다.

• 나누어 떨어진다면, K가 만들어지지 않은 일은 일어나지 않으므로, 1에서 사용하지 않은 하나의 동전을 사용해도 되기 때문이다.
• 이때, K를 동전 금액만큼 차감한다.

3. 1~2를 K가 만들어질 때까지 반복한다.

 

두서없이 쓴 것 같아서... 예제를 가져와봤다.

for (int i = len - 1; i >= 0; i--)
{
    // 목표 금액 달성 했다면 반복문 나가기
    if (k == 0) break;

    // 동전이 목표 남은 목표 금액보다 크다면 다음 동전으로
    if (coins[i] > k) continue;

    int div = k / coins[i];

    // 마지막 동전이라면 합이 k가 될 때까지 모두 사용하고,
    // 그렇지 않다면 최대한 사용할 수 있는 바로 전 단계까지만
    int offset = (i == 0) ? 0 : -1;

    k -= (div + offset) * coins[i];
    answer += div + offset;

    for (int j = i - 1; j >= 0; j--)
    {
        if (j < 0) break;

        // 만약 사용할 수 있는 만큼 사용할 때
        // 후에 남기지 않고 사용할 수 있으면
        if ((k - coins[i]) % coins[j] == 0)
        {
            // 사용하지 않은 하나의 코인도 바꿔준다
            k -= coins[i];
            answer++;
            break;
        }
    }
}

cout << answer;

 

조금 길고 가독성이 떨어지는 코드이긴 하다...

 

재미있고 유익한 문제였다. 그리디를 푸는 사고력이 점점 느는 것 같아서 기분이 좋다.