글 읽기 - ★3067번 시간초과 해결법 요망★

hhr8540 3년 전 0

배낭 문제 (knapsack)에서 아이디어를 얻어서 재귀함수로 풀었습니다.

테스트케이스 정답은 잘 나오는데 자꾸만 시간초과가 뜹니다..

어떻게 시간초과가 나는 이유와 어떻게 해결방향을 잡으면 좋을지 조언 부탁드리겠습니다.

#include <stdio.h>

int n;
int knapsack;
int jewelry[21];
int dp[30001][21];

void input() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &jewelry[i]);

	scanf("%d", &knapsack);
}

void clear() {
	for (int i = 0; i < knapsack; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = 0;
		}
	}
}

int go(int w, int s) {

	if (dp[w][s] > 0) return dp[w][s];

	if (w > knapsack) return 0;
	else if (w == knapsack) return 1;
	
	int ans = 0;
	for (int i = s; i < n; i++) {
		ans += go(w + jewelry[i], i);
	}

	return dp[w][s] = ans;
}


int main() {

	int T;
	scanf("%d", &T);

	while (T--) {

		input();
		printf("%d\n", go(0, 0));
		clear();

	}

	return 0;
}

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

문제

문제

출처

ICPC

★3067번 시간초과 해결법 요망★

hhr8540 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말