글 읽기 - c++ 시간초과

rhrkddus 2년 전 0

어디서 시간 초과가 나는지 잘 모르겟어용 ㅠㅠ

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int knap2(int n, int W, int** val)
{
	
	if (n<= 0 || W <= 0)
	{
		return 0;
	}
	if (val[0][n] > W)
	{
		return knap2(n - 1, W, val);
	}

	else {
		 
		
		
		int maxp = max(knap2(n - 1, W, val), knap2(n - 1, W - val[0][n], val) + val[1][n]);
		
		

		return maxp;

	}
}


int main()
{
	int n, k;
	int w, v;
	

	cin >> n >> k; // 개수 , 무게
	
	
	// 무게 ,가치 , 무게당 가치 있는 배열 만들고 무게당 가치로 소팅??

	int** val1 = new int* [2];
	for (int i = 0; i < 2; i++)
	{
		val1[i] = new int[n+1];
	}
	// 할당
	for (int i = 0; i < n; i++)
	{
		cin >> w >> v;
		val1[0][i+1] = w;
		val1[1][i+1] = v;
		
 	}
	
	

	cout << knap2(n, k, val1);
	

	

}

kdh6429 2년 전 0

최적화 문제입니다. knap2 의 함수가 동일한 파라미터로 여러번 호출될수 있습니다. 메모이제이션을 활용하여 재귀호출로 인한 연산 수를 줄여보세요.

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

문제

문제

출처

ICPC

c++ 시간초과

rhrkddus 2년 전 0

kdh6429 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말