백준 11047번 [동전 0](C++) -yes6686- 티스토리

 

백준 문제 풀이: 11047 [동전 0]

---

문제 링크: https://www.acmicpc.net/problem/11047

문제 설명:

각각의 동전을 사용하여 총 금액 K를 맞추는 최소 동전 개수를 계산하세요. 동전은 무제한으로 사용할 수 있습니다.

입력 조건:

• 첫째 줄에 N과 K가 주어집니다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
• 둘째 줄부터 N개의 줄에 동전의 가치가 오름차순으로 주어집니다. (1 ≤ 동전 가치 ≤ 1,000,000)
• 주어진 동전의 가치는 서로 다릅니다.

출력 조건:

• K원을 만드는데 필요한 동전 개수의 최솟값을 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[11];

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    int cnt = 0;
    for (int i = n; i >= 1; i--) {
        if (k == 0) break; // 필요한 금액이 0이면 종료
        if (arr[i] <= k) { // 현재 동전으로 나눌 수 있는 경우
            cnt += (k / arr[i]); // 필요한 동전 개수 추가
            k %= arr[i]; // 남은 금액 갱신
        }
    }

    cout << cnt << '\n'; // 최소 동전 개수 출력
    return 0;
}
    

---

코드 설명

위 코드는 그리디 알고리즘을 사용하여 총 금액 K를 만들기 위해 필요한 최소 동전 개수를 계산합니다.

• 입력 처리:
  • 배열 `arr`에 각 동전의 가치를 저장합니다.
  • 큰 동전부터 사용할 수 있도록 입력된 동전을 역순으로 처리합니다.
• 그리디 알고리즘:
  • 큰 가치의 동전부터 선택하여 필요한 금액 `k`를 나눕니다.
  • 해당 동전을 사용한 후, 나머지 금액을 `k`에 갱신합니다.
• 최적화:
  • 필요한 금액이 `0`이 되면 루프를 종료하여 불필요한 연산을 방지합니다.

시간 복잡도 분석:

• 동전 개수 N에 대해 한 번의 루프: O(N).

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

출력:
6
    

주어진 입력에 따라 총 6개의 동전을 사용하여 4200원을 만들 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!