백준 11047_동전 0

문제 링크

문제 한 줄 요약

N종류 동전의 최소 개수로 K를 만들어라. (동전의 개수가 무한대이므로 만들 수 없는 경우는 존재하지 않는다.)

내가 생각한 조건

최소 개수라 했으므로 입력받은 N을 오름차순으로 정렬한 후, 가장 많은 값부터 넣어가면서 비교하면 될 것 같았다.
(오름차순이라 정의되어 있으므로 다시 정렬할 필요는 없음.)
가장 많은 값부터 임의로 넣어가며 작업하면 될 것이라 생각했기 때문에 해당 상황에서 가장 적합한 값을 찾는 그리디 알고리즘이 적합할 것이라 생각했다.

작성한 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){
    int n, k;
    vector<int> v;
    int ans = 0;
 
    cin >> n >> k;
 
    for(int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
    
    int v_size = v.size()-1;
    int sub_cal = 0;
 
    for(int i = v_size; i >=0; i--)
    {
        if(v[i] > k) 
            continue;
        else if(v[i] == k) 
        {
            ans += 1;
            break;
        }
        else if(v[i] < k)
        {
            while(sub_cal < k){
                sub_cal = sub_cal + v[i];
                ans += 1;
                
            }
            if(sub_cal == k) break;
            sub_cal -= v[i];
            ans -= 1;
            continue;
        }
        
    }
    cout << ans << '\n';
 
}

코드 작성 후 피드백

이 블로그 게시글을 참고했다.
나는 직관적으로 값을 계속 빼주는 값으로 계산했다.
그러나 예시를 들어 생각해 보았을 때, 2200원에서 1000원짜리는 2개를 쓰고 200원이 남는다.
이 말은 값을 나눠서 횟수를 구한 후, k는 %연산자를 사용해 갱신해주면 된다는 뜻이다.

이를 바탕으로 for문을 정리해보면 다음과 같다.

int suc_cal = 0;
for (i = n-1; i >= 0; i--)
{
    sub_cal += k / v[i];
    k %= v[i];
}

그리고 작성 코드를 보면 else if문에서 계산을 할 때 N과 K의 대소를 비교해서 if문을 작성하고, while문에서 무조건 N값을 더해주며 계산했기 때문에 while문을 빠져나올 경우 추가로 처리해야 하는 연산이 존재해서 비효율적이었다. (그리고 이후 K와 같을 때 조건문을 반드시 넣어서 조건을 따져줬기 때문에 비효율적)

참고 코드를 이용하면 k값이 실시간으로 바뀌어서 k=0이 되면 자동으로 해결이 된 것이기 때문에 굳이 복잡하게 식을 넣지 않아도 된다.

한줄평

너무 직관적으로만 코드를 작성한 것 같다. 좀 더 코드 내부에 있는 공식을 생각하는 습관을 가져야 할 것 같다.

### **Point** 그리디 알고리즘은 각 단계에서 가장 최선의 선택을 하는 방법이다. (그 방법을 가장 직관적으로 활용한 문제이다.) 특정 값 A를 주어진 값 B들을 사용해 조합하는 문제의 경우 **/, %연산자**를 떠올리자.