Exact Change

문제

Problem - D - Codeforces

1원짜리, 2원짜리, 3원짜리 동전만 사용가능할 때 물건의 가격이 n개 주어지면 

가장 최소한의 동전 갯수로 n개의 물건중 아무거나 1개 살 수 있을때 최소한의 동전 갯수를 구하는 문제입니다.

가격은 거스름돈 없이 정확히 맞아 떨어져야 합니다.

예를 들어 n = 3이고 물건의 가격들이 각각 10,  8,  10 이라면 

최소한의 동전 갯수는 2원짜리 2개 + 3원짜리 2개 로 (2, 2, 3, 3) 8원도 살 수 있고 10원도 살 수 있습니다.

따라서 최소 동전 갯수는 4개 입니다.

 

필요한 동전의 개수를 최소화 하는 것이기 때문에 3원짜리 동전이 많이 있으면 좋습니다.

따라서 3원짜리 동전을 최대화하고 나머지 가격은 3원보다 낮을 것이므로 1원과 2원의 조합으로 최소화하는 것입니다.

 

따라서 우리는 동전 1원과 2원으로 만들 수 있는 조합을 따로 생각해 주어야 합니다.

이는 2차원 벡터로 표현 가능합니다. 

예를 들어 can[i][j] = 1원짜리 동전이 i개, 2원짜리 동전이 j개 있다는 의미입니다.

for (int i = 0; i < 3; i++)
	for (int j = 0; j < 3; j++)
		can[i][j].push_back(0);

can[1][0].push_back(1);
can[0][1].push_back(2);
can[1][1].push_back(1);
can[1][1].push_back(2);
can[1][1].push_back(3);
can[2][0].push_back(1);
can[2][0].push_back(2);
can[0][2].push_back(2);
can[0][2].push_back(4);
can[2][1].push_back(1);
can[2][1].push_back(2);
can[2][1].push_back(3);
can[2][1].push_back(4);
can[1][2].push_back(1);
can[1][2].push_back(2);
can[1][2].push_back(3);
can[1][2].push_back(4);
can[1][2].push_back(5);
can[2][2].push_back(1);
can[2][2].push_back(2);
can[2][2].push_back(3);
can[2][2].push_back(4);
can[2][2].push_back(5);
can[2][2].push_back(6);

can[][] 함수에 처음에 모두 0을 삽입하는 이유는 1원과 2원 모두 사용하지 않을 경우도 있기 때문입니다.

(가격이 3의 배수 일때)

---

while (t--) {
        cin >> n;
        vector<ll>v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
        ans = inf;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                a = 0; //최대 3원 동전의 갯수
                for (int k = 0; k < n; k++) {
                    sum = inf; //최소 1원과 2원의 
                    for (auto nxt : can[i][j]) {
                        if (v[k] < nxt)continue;
                        if ((v[k] - nxt) % 3 == 0)sum = min(sum, (v[k] - nxt) / 3);
                    }
                    a = max(a, sum);
                }
                ans = min(ans, a + i + j);
            }
        }
        cout << ans << '\n';
    }

최대 시간복잡도는 3 * 3이며 a를 통해 3의 최대 갯수를 구한뒤 ans를 통해 1원동전 i개와 2원동전 j개의 최소 조합을

구합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<ll>can[3][3];
ll ans;
ll a, sum;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    int n;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            can[i][j].push_back(0);
 
 
    can[1][0].push_back(1);
    can[0][1].push_back(2);
    can[1][1].push_back(1);
    can[1][1].push_back(2);
    can[1][1].push_back(3);
    can[2][0].push_back(1);
    can[2][0].push_back(2);
    can[0][2].push_back(2);
    can[0][2].push_back(4);
    can[2][1].push_back(1);
    can[2][1].push_back(2);
    can[2][1].push_back(3);
    can[2][1].push_back(4);
    can[1][2].push_back(1);
    can[1][2].push_back(2);
    can[1][2].push_back(3);
    can[1][2].push_back(4);
    can[1][2].push_back(5);
    can[2][2].push_back(1);
    can[2][2].push_back(2);
    can[2][2].push_back(3);
    can[2][2].push_back(4);
    can[2][2].push_back(5);
    can[2][2].push_back(6);
 
    while (t--) {
        cin >> n;
        vector<ll>v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
        ans = inf;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                a = 0;
                for (int k = 0; k < n; k++) {
                    sum = inf;
                    for (auto nxt : can[i][j]) {
                        if (v[k] < nxt)continue;
                        if ((v[k] - nxt) % 3 == 0)sum = min(sum, (v[k] - nxt) / 3);
                    }
                    a = max(a, sum);
                }
                ans = min(ans, a + i + j);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}