글 읽기 - 카드게임 48%에서 시간초과 네이놈

godvicii 6년 전 0

메모이제이션으로 풀었습니다.

근데 48%정도에서 시간초과가 납니다.

시간을 지배하는 고수님들 봐주세요..

#include <stdio.h>
#define max(a,b) (((a)>(b))? (a) : (b))
int D[2001][2001];
int l[2001], r[2001], N;
//int max(int a, int b) { return a > b ? a : b; }
int solve(int left, int right)
{
	if (left >= N || right >= N)
		return 0;
	if (D[left][right])
		return D[left][right];
	if (l[left] > r[right])
		D[left][right] = solve(left, right + 1) + r[right];
	else {
		//D[left][right] = max(solve(left + 1, right), solve(left + 1, right + 1));
		int a = solve(left + 1, right);
		int b = solve(left + 1, right + 1);
		D[left][right] = max(a, b);
	}
	return D[left][right];
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &l[i]);
	for (int i = 0; i < N; i++)
		scanf("%d", &r[i]);

	printf("%d", solve(0, 0));
}

chogahui05 6년 전 1

간단하게 아래 데이터를 넣어봅시다.

테스트 결과가 어떻게 나오나요?

/*
30
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
*/

godvicii 6년 전 0

대단하시네요. 0이 되는 케이스는 생각하지 못했네요. 감사합니다.

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

문제

문제

출처

ICPC

카드게임 48%에서 시간초과 네이놈

godvicii 6년 전 0

chogahui05 6년 전 1

godvicii 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말