글 읽기 - 왜 틀렸다고 나오는지 모르겠습니다.

saeugsa_uka 7년 전 0

안녕하세요.

숫자와 곱셈을 나열하면서, 그 값을 계산하여 찾는 값이 나왔을 때 곱셈의 최소의 개수를 구하도록 구현했는데요.

테스트 케이스는 잘나오는데 시간초과도 아니고 틀렸다고 나옵니다. 반례가 뭐가 있을까요?

#pragma warning(disable:4996)
#include <iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>

using namespace std;


vector<int> L;
int cache[1000001];
int total;
int fun(int sum) {

	if (sum > total) return 987654321;
	if (sum == total)  return 0;
	int &ret = cache[sum];
	if (ret != -1)return ret;
	ret = 987654321;
	for (int i = 0; i < L.size(); ++i) {
		if (L[i] == 0 && sum == 0)continue;
		else if (L[i] == 0)ret = min(ret, fun(sum * 10));
		else if (L[i] == 1 || sum == 0)ret = min(ret, fun(sum * 10 + L[i]));
		else ret = min(ret, min(fun(sum * 10 + L[i]), fun(sum*L[i]) + 1));
	}

	return ret;
}
int main() {
	int t;

	cin >> t;
	while (t--) {
		total = -1;
		L.clear();
		int a, m;
		cin >> a;

		for (int i = 1; i <= a; ++i) {
			int x;
			scanf("%d", &x);
			L.push_back(x);
		}

		cin >> m;
		for (int i = 1; i <= m; ++i) {
			for (int i = 0; i <= 1000000; ++i)cache[i] = -1;
			int x;
			int ret ;
			scanf("%d", &x);
			total = x;
			ret = fun(0);
 			ret == 987654321 ? printf("%d\n", -1) : printf("%d\n", ret);
		}
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸다고 나오는지 모르겠습니다.

saeugsa_uka 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말