글 읽기 - 틀린이유 좀 찾아주세요;;

ghkdtkden93 7년 전 0

시간초과도 안나고 실행결과도 잘나옵니다...

근데 틀렸답니다... dp써서 괜찮을 줄 알았는데..

#include <cstdio>
#include <iostream>
using namespace std;
unsigned long long recursive(int *, int, int, int);
int main()
{
	int N;
	scanf("%d", &N);
	int *arr = new int[N];
	for (int i = 0; i < N; i++)
		scanf("%d", arr + i);
	cout << recursive(arr, arr[0], 1, N) << endl;
	return 0;
}
unsigned long long recursive(int *arr, int sum, int idx, int N)
{
	static unsigned long long memo[100][21];
	if (sum > 20 || sum < 0)
		return 0;
	if (idx == N - 1)
		if (arr[idx] == sum)
			return 1;
	if (memo[idx][sum] > 0)
		return memo[idx][sum];
	memo[idx][sum] += recursive(arr, sum + arr[idx], idx + 1, N);
	memo[idx][sum] += recursive(arr, sum - arr[idx], idx + 1, N);
}

portableangel 7년 전 1

26~27번 줄 사이에 return memo[idx][sum]; 이 빠졌네요.

그 외에, 답이 0인 케이스에는 DP가 영향력을 못 발휘해(0인 케이스는 계산되지 않은 것으로 간주해 중복 계산합니다) 시간초과가 날 듯합니다.

캐시를 그냥 long long으로 선언해주시고, 적당한 음수값으로 초기화해주신 다음 0 이상이면 리턴하도록 바꿔주시면 되겠네요.

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

문제

문제

출처

ICPC

틀린이유 좀 찾아주세요;;

ghkdtkden93 7년 전 0

portableangel 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말