글 읽기 - 시간 초과가 나는 이유가 뭘까요..?

rmrf 6년 전 0

9% 정도에서 시간 초과가 나네요..

#include <iostream>
#include <algorithm>
#include <array>
#include <cstdio>

using namespace std;

int cache[10001];
int coins[100];
int N, K;

void init();
int getCoins(int remain);

int main(void) {
	scanf("%d%d", &N, &K);
	init();
	for(int i = 0; i < N; ++i) {
		scanf("%d", &coins[i]);
		if(coins[i] > K) continue;
		cache[coins[i]] = 1;
	}
	sort(coins, coins + N);
	printf("%d", getCoins(K));
	return 0;
}

void init() {
	for(int k = 0; k < K + 1; ++k)
		cache[k] = -1;
}

int getCoins(int remain) {
	int min = -1;
	int tmp;
	if(cache[remain] != -1) {
		return cache[remain];
	}
	for(int i = 0; i < N; ++i) {
		if(remain >= coins[i]) {
			tmp = getCoins(remain - coins[i]);
			if(tmp == -1) continue;
			if(min == -1) min = tmp + 1;
			else if(min > tmp + 1) min = tmp + 1;
		}
		else break;
	}
	return cache[remain] = min;
}

chogahui05 6년 전 0

cache[remain-coins[i]]의 값이 -1인 경우에 문제가 될 거 같은데요.. 이 경우에는 이미 탐색한 경우라도 중복 계산이 될 수 있으니까요.

초기화 값을 다르게 줘 보세요. 2147483647이라던지..

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

문제

문제

출처

ICPC

시간 초과가 나는 이유가 뭘까요..?

rmrf 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말