글 읽기 - ㅁㄴ이ㅣ라ㅓㅏ 시간초과 ㅠㅠㅠ 도와주세염...

bw2218 7년 전 0

Coin함수는 최소 동전의 갯수를 반환해주는 함수고

메모이제이션까지 햇는데 시간초과 나요 ㅠㅠㅠㅠ

도와주세요!!!

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace::std;
int n, k;
int memo[101];
int cache[101][10001];

int Coin(int n, int Sum) // n, k 값
{
	int temp = 999999999;
	if (Sum == 0)
		return 0;
	if (n == 0)
	{
		if (Sum%memo[0] != 0)
			return -1;
		else
			return Sum / memo[0];
	}
	if (cache[n][Sum] != -1)
		return cache[n][Sum];

	int c = Sum / memo[n];
	for (int i = c; i >= 0; i--)
	{
		int result = Coin(n - 1, Sum - i*memo[n]);
		if (result < 0) continue;
		temp = min(temp, result + i);
	}
	if (temp >= 999999999)
		return cache[n][Sum] = -1;
	else return cache[n][Sum] = temp;
}
int main(void)
{
	memset(memo, 0, sizeof(memo));
	memset(cache, -1, sizeof(cache));
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> memo[i];
	cout << Coin(n - 1, k);	
	return 0;
}

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

문제

문제

출처

ICPC

ㅁㄴ이ㅣ라ㅓㅏ 시간초과 ㅠㅠㅠ 도와주세염...

bw2218 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말