글 읽기 - 왜 틀린지 모르겠네요 ㅠㅠ

isco 5년 전 0

질문게시판에 있는 반례 넣어도 다 맞게 나오고 답이 없는 경우 -1 출력하는 처리까지 했는데 왜 틀린지 모르겠습니다.

고수님들 도와주십쇼 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
using namespace std;

int n, k;
const int INF = 987654321;
int coins[100];
int cache[10000];

/*int solution(int num, int sum)
{
	if (sum == k) return num;
	int ret = INF;
	for (int i = 0; i < n; ++i)
	{
		if (sum + coins[i] <= k) ret = min(ret, solution(num + 1, sum + coins[i]));
	}
	return ret;
}*/

int solution(int sum)
{
	if (sum == 0) return 0;
	int& ret = cache[sum];
	if (ret != -1) return ret;
	ret = INF;
	for (int i = 0; i < n; ++i)
	{
		if (sum - coins[i] >= 0) ret = min(ret, 1 + solution(sum - coins[i]));
	}
	return ret;
}

int main() 
{
	memset(cache, -1, sizeof(cache));
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &coins[i]);
	}
	//printf("%d\n", solution(0, 0));
	int ans = solution(k);
	printf("%d\n", ans != INF ? ans : -1);
	return 0;
}

djm03178 5년 전 0

cache에는 10000번째 원소가 없습니다.

isco 5년 전 0

아 캐시를 10001로 안하고 10000으로 했네요 ㅡㅡ; 해결했습니다.

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

문제

문제

출처

ICPC

왜 틀린지 모르겠네요 ㅠㅠ

isco 5년 전 0

djm03178 5년 전 0

isco 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말