C - [백준 11047] 동전 0 (feat. 탐욕알고리즘)

2025.02.02 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

[자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

 

 

 

---

동전 0 (백준 11047번) 문제 풀이

문제 설명

N개의 종류의 동전이 있고, 각 동전의 가치가 주어집니다. 이 동전들을 이용하여 합이 K가 되도록 할 때, 필요한 동전의 최소 개수를 구하는 문제입니다. 동전의 가치는 항상 오름차순으로 주어지며, 모든 동전의 가치는 서로 다릅니다.

문제 링크: 백준 11047번 동전 0

---

Checkpoint

이 문제는 그리디 알고리즘을 활용하여 해결할 수 있습니다. 동전의 가치가 높은 순서대로 최대한 많은 동전을 사용하여 K를 빠르게 줄이는 방식으로 접근합니다.

그리디 알고리즘 적용 이유

1. 동전의 가치가 서로 다르고 오름차순으로 주어지기 때문에, 큰 가치의 동전부터 사용하면 최적의 해를 보장할 수 있습니다.
2. 최적 부분 구조를 가지며, 부분 문제의 최적 해가 전체 문제의 최적 해에 포함됩니다.

---

구현 알고리즘

1. 동전 리스트를 내림차순으로 정렬합니다.
2. 큰 동전부터 K를 나누어 최대한 많은 동전을 사용합니다.
3. 동전 사용 개수를 누적합니다.
4. 모든 동전을 순회하여 K가 0이 되면 종료합니다.

---

코드 구현

#include <stdio.h>

int main() {
    int N, K;
    int coins[10];  // 최대 10개의 동전 종류
    int count = 0;

    // 동전 종류와 목표 금액 입력
    scanf("%d %d", &N, &K);

    // 동전 가치 입력
    for (int i = 0; i < N; i++) {
        scanf("%d", &coins[i]);
    }

    // 큰 동전부터 사용
    for (int i = N - 1; i >= 0; i--) {
        if (coins[i] <= K) {
            count += K / coins[i];  // 해당 동전으로 몇 개를 사용할 수 있는지 계산
            K %= coins[i];          // 남은 금액 계산
        }
    }

    // 결과 출력
    printf("%d\n", count);

    return 0;
}

---

코드 설명

1. 입력 처리:
   N과 K를 입력받고, coins 배열에 동전 가치를 저장합니다.
2. 그리디 적용:
   동전 배열을 역순으로 순회하면서 현재 동전이 K보다 작거나 같을 때 최대한 많이 사용합니다.
   • 사용한 동전 개수를 count에 누적합니다.
   • 사용 후 남은 금액을 K %= coins[i]로 갱신합니다.
3. 결과 출력:
   모든 동전을 순회한 후, 최소 동전 개수를 출력합니다.

---

예제 입력과 출력

입력 예시

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

출력 예시

6

설명:

• 5000원 동전 1개 사용 → 남은 금액 4200 - 5000 = 4200
• 1000원 동전 4개 사용 → 남은 금액 4200 - 4000 = 200
• 100원 동전 2개 사용 → 남은 금액 200 - 200 = 0
  총 6개의 동전을 사용하여 문제를 해결했습니다.

---

핵심 정리

• 이 문제는 큰 가치의 동전부터 사용하는 그리디 알고리즘으로 해결할 수 있습니다.
• 시간 복잡도는 동전의 개수 N에 비례하는 O(N)입니다.
• 동전의 가치가 서로 다르고 오름차순으로 주어지는 점을 활용하면 최적해를 보장할 수 있습니다.

---