[학습동아리] 6일차 08/10

활동일시 : 6일차 2023-08-10 21:30-23:30

---

목표

c++, python으로 백준 실버5 티어 이상의 알고리즘 문제 풀기

동전 0

---

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

코드

python

import math

N, K = map(int, input().split())
arr = []

for i in range(N):
    arr.append(int(input()))

total = 0
arr.reverse()
while True:
    for i in range(N):
        if arr[i] <= K:
            cnt = math.floor(K / arr[i])
            total += cnt
            K -= cnt * arr[i]
            break

    if K == 0:
        break
print(total)

c++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int N;
    int K;
    cin >> N >> K;

    vector<int> v;

    for (int i = 0; i < N; i++) {
        int k;
        cin >> k;
        v.push_back(k);
    }

    int total = 0;

    while (true) {
        for (int i = N-1; i >= 0; i--) {
            if (v[i] <= K) {
                int cnt = floor(K / v[i]);
                total += cnt;
                K -= cnt * v[i];
                break;
            }
        }

        if (K == 0) {
            break;
        }
    }

    cout << total << endl;

    return 0;
}

---

풀이

문제를 해결하기 위한 기본 로직은 주어진 동전을 가치가 큰 것부터 순차적으로 K에서 빼면서 동전의 개수를 계산한다.

1. 동전의 가치를 내림차순으로 정렬(c++에서는 정렬이 아닌 벡터의 뒤에서부터 읽는것으로 대체)
2. 가치가 가장 큰 동전부터 시작하여, 해당 동전의 가치가 K보다 작거나 같은 경우 해당 동전을 얼마나 사용 할 수 있는지 센다.
3. 총 몇개의 동전을 사용하는지 알기 위해 사용한 동전의 수를 총 동전의 수에 더한다.
4. K에서 해당 동전 가치를 뺀다.
5. 위 과정을 모든 동전에 대해 반복한다.

---

느낀점

4주차때는 그리디 알고리즘은 유독 풀이가 잘 떠오르지 않는다고 느꼈었는데, 4주차때 학습한 결과인지 오늘은 바로 풀이가 떠올라서 쉽게 풀고 c++ 코드로도 바꿔보았다.
기본적인 수준은 풀 수 있게 된 것 같아서 이번주차로 그리디 알고리즘은 마무리하고, 다음주차때는 어렵게 느껴져서 1학년때부터 미루고 미뤘던 dfs와 bfs를 공부해보아야겠다.