[C++] 1257번 엄청난 부자 - 수학, 데이크스트라, 그리디

1257번 엄청난 부자

 

1. 문제

• 최백준 조교는 그가 가진 금액을 동전으로 교환하되, 그 개수를 최소화하고자 한다.

<입력>

• -1- 최백준 조교가 가진 금액 \(M(10^9 \leq M \leq 10^18)\)
• -2- 동전의 종류 \(N(1 \leq N \leq 1,000)\)
• -3- 동전의 금액 \(A_i(1 \leq A_i \leq 10,000)\)가 N개 주어진다.
• N가지의 동전 중 1원짜리 동전은 항상 존재한다.

<출력>

• 동전으로 딱 맞는 금액을 만들 때, 그 최소 개수를 출력하라.

 

2. 재정의

• X

 

3. 해결 방법

• \(M = A[N-1] \times x + r)\)로 나타내어질 수 있고 10,000*10,000은 \(10^9\)보다 작기 때문에 나머지가 r이되도록 동전의 개수를 최소화 하고 나머지는 A[N-1]로 더하는 방법으로 그리디를 할 수 있다.

 

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

typedef long long int lld;
typedef pair<int, int> pii;

const int INF = 987654321;
const int MAX_N = 1001;
const int MAX_C = 10001;

lld M;
int N;
int A[MAX_N];
vector<pii> vertex[MAX_C];
int dist[MAX_C];

struct cmp {
    bool operator()(int a, int b) {
        return dist[a] > dist[b];
    }
};

priority_queue<int, vector<int>, cmp> pq;

void input() {
    fill(dist, dist + MAX_C, INF);
    
    cin >> M;
    cin >> N;
    for(int i=0; i<N; i++)
        cin >> A[i];
    sort(A, A + N);
}

void solve() {
    dist[0] = 0;
    for(int i=0; i<A[N-1]; i++) {
        for(int j=0; j<N-1; j++) {
            int v = i + A[j], c = v<A[N-1];
            vertex[i].push_back({v%A[N-1], c});
        }
    }
    
    pq.push(0);
    while(!pq.empty()) {
        int t = pq.top(); pq.pop();
        for(auto x : vertex[t]) {
            int v = x.first, c = x.second;
            if(dist[t] + c < dist[v]) {
                dist[v] = dist[t] + c;
                pq.push(v);
            }
        }
    }
    
    cout << M/A[N-1] + dist[M%A[N-1]];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

 

<문제 바로가기>

https://www.acmicpc.net/problem/1257

1257번: 엄청난 부자