글 읽기 - 이해가 안가는 시간초과...

his130 6년 전 0

시간초과가 발생하는 이유가 뭘까요..

아무리 생각해도 모르겠습니다...ㅠㅠ

아래코드로 푸니까 맞았습니다, 위의 코드는 시간초과..

1520번 문제와 비슷하게 초기값 문제인거 같은데.. 1520은 이해가 가는데

이 문제는 도통 이해가 가질 않네요..

점화식 D[K] 는 K를 만드는 방법의 수의 최솟값입니다..

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int n, k;
vector<int> coin;
int D[10001];


int go(int K)
{
	if (K == 0)
	{
		return 0;
	}
	if (D[K] != 987654321)
	{
		return D[K];
	}


	for (int i = 0; i < coin.size(); i++)
	{
		if (K - coin[i] >= 0)
		{

			D[K] = min(D[K], go(K - coin[i]) + 1);

		}
	}

	return  D[K];
}
int main()
{
	scanf("%d %d", &n, &k);
	coin.resize(n);
	for (int i = 0; i < 10001; i++)
	{
		D[i] = 987654321;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &coin[i]);
	}
	sort(coin.begin(), coin.end());
	reverse(coin.begin(), coin.end());
	
	int ans = go(k);

	if (ans == 987654321)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n", ans);
	}
	


	return 0;
}



/////////////////////////////////////////////////////////////////////



#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int n, k;
vector<int> coin;
int D[10001];

int go(int K)
{
	if (K == 0)
	{
		return 0;
	}
	if (D[K] != -1)
	{
		return D[K];
	}

	if (D[K] == -1)
	{
		D[K] = 987654321;
	}
	for (int i = 0; i < coin.size(); i++)
	{
		if (K - coin[i] >= 0)
		{
			D[K] = min(D[K], go(K - coin[i]) + 1);
		}
	}

	return  D[K];
}
int main()
{
	scanf("%d %d", &n, &k);
	coin.resize(n);
	for (int i = 0; i < 10001; i++)
	{
		D[i] = -1;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &coin[i]);
	}
	sort(coin.begin(), coin.end());
	reverse(coin.begin(), coin.end());

	int ans = go(k);

	if (ans == 987654321)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n", ans);
	}



	return 0;
}

his130 6년 전 0

아...

혹시 방문안함과 방문했지만 방법이 없다를 나누는 건가요?

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

문제

문제

출처

ICPC

이해가 안가는 시간초과...

his130 6년 전 0

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말