CPSCO2019 Session1 C - Coins

未解決

https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_c

問題概要

1, 10, 100, ..., 109, 5, 50, 500, ..., 5 * 109円硬貨がある
スーパーでN種類の果物が1つずつ、それぞれA0,A1, ..., An-1円で売られている

N種類の果物のうち、K個買う時の合計金額をちょうど支払うために必要な硬貨の枚数の最小値を求めよ
ただし、硬貨の数は限りなく多いとする

制約

1 ≤ N ≤ 32
1 ≤ K ≤ min(N,6)
1 ≤ Ai ≤10^8
入力はすべて整数

考えたこと

再帰関数問題だということはあらかじめわかっていた状態でのスタート。再帰関数に渡したデータは４つで、果物の値段の情報、合計金額の情報、もう一度同じものを選ばないようにするための処理、何回選んだかのカウント。正直あってると思っていた。超ごり押しだけど。結果は2WA,14TLE。処理が重すぎたのだろうか？分からない。

こーど

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int N;
int K;
vector<int> mendoi;

int kaunnto(int sum) {
	string str10 = "1000000000";
	string str50 = "5000000000";

	int count = 0;
	bool can50 = true;

	while (1) {


		if (can50) {
			unsigned long long num = stoull(str50);
			if (sum / num != 0) {
				count++;
				sum %= num;
			}
			str50.pop_back();


			can50 = false;
		}
		else {
			unsigned long long num = stoull(str10);
			if (sum / num != 0) {
				count += sum / num;
				sum %= num;
			}
			if (str10 == "1") {
				return count;
			}
			str10.pop_back();

			can50 = true;
		}

	}
}

void coin(vector<int> A, int sum, int kaisuu, vector<int> erabu) {

	if (kaisuu == K) {
		int count = 0;

		count = kaunnto(sum);

		mendoi.push_back(count);
		return;
	}

	for (int i : erabu) {
		sum += A[i];
		auto it = find(erabu.begin(), erabu.end(), i);
		erabu.erase(it);
		kaisuu++;
		coin(A, sum, kaisuu, erabu);
		kaisuu--;
		erabu.push_back(i);
		sum -= A[i];
	}
}

int main() {

	cin >> N;
	cin >> K;

	vector<int> erabu;
	vector<int> A(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> A[i];//変更可能性なし参照データ
		erabu.push_back(i);
	}


	int sum = 0;
	int kaisuu = 0;
	coin(A, sum, kaisuu, erabu);

	sort(mendoi.begin(), mendoi.end());
	cout << mendoi[0];

}

ほかの人のこーどをみてみた。

参考にしたサイト>なかった..
終わり。