글 읽기 - 시간초과 해결 방법

ghkdtkden93 7년 전 0

recursive 로 하니깐 역시 시간이 많이 걸리네요

dp로 해보려했는데 감이 잘 안잡히네요... dp로한다면 어떻게하는지

아니면 다른방법이 있는지 가르쳐주세요

0~9까지의 숫자만 입력된다는 게 힌트 같은데

중간에 음수 와 20이 초과되지않는 수는 안된다는 조건을 충족을 못시키겠네요.

#include <cstdio>
void recursive(int *,int ,int ,int );
static int cnt;
int main()
{
	int N;
	scanf("%d",&N);
	int *arr = new int[N];
	for (int i = 0; i < N ; i++)
		scanf("%d", arr + i);
	recursive(arr, 0, 0, N);
	printf("%d\n",cnt);
	return 0;
}
void recursive(int *arr,int sum , int idx , int N)
{
	if (sum > 20 || sum < 0)
		return;
	if (idx == N - 1)
	{
		if (arr[idx] == sum)
			cnt++;
		return;
	}
	recursive(arr, sum + arr[idx], idx + 1,N);
	recursive(arr, sum - arr[idx], idx + 1,N);
	return;
}

onjo0127 7년 전 5

메모이제이션이라고 DP를 재귀적으로 풀 때 결과가 같은 함수를 중복 호출하지 않게 배열에 저장해놓는 기법이 있습니다.

memo 배열을 하나 만들어서

memo[sum][idx] 에 sum, idx를 인자로 하는 함수를 호출한 적 있는지의 여부를 저장해놓고 이미 이 함수를 호출한 적이 있다면 해당 함수를 종료하면 됩니다.

이렇게 시간을 줄여 주면 시간 내에 해결가능합니다.

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

문제

문제

출처

ICPC

시간초과 해결 방법

ghkdtkden93 7년 전 0

onjo0127 7년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말