글 읽기 - 최대증가부분수열 문제 질문입니다.

mushi 7년 전 0

알고스팟에서 유사 문제 입력수 max 500에서는 12~14ms 로 통과 하였습니다만
입력수 max1000인 11053번 문제는 타임초과네요.

여러 경우의 수를 생각해서 break를 넣어 시간을 줄이려고 노력 했으나 더이상은 생각이 안나네요.

현 코드로는 더이상의 시간 절약이 안될까요??

#include <stdio.h>
#include <string.h>

#define MAX 1001
#define max(a, b) a>b? a:b

int cache[MAX];
int arr[MAX];
int t, n;
int lis=0;
int max_num=0;

void Lis()
{
	int i, j;
	int ret=1;
	
	for(i=n-2; i>=0; i--)
	{
		for(j=i+1; j<n; j++)
		{
			max_num=max(max_num, arr[i]);
			if(arr[i]>=max_num)//가장 큰 수면 비교 불 필요
				break;
            //i가 큰수고 비교대상(j)이 길이1이면 그 뒤로 다 i보다 작은 수, 비교 불필요
			if(arr[i]>=arr[j] && cache[j]==1)
				break;
			if(arr[i]>=arr[j])
				continue;
			ret+=cache[j];
			cache[i]=max(cache[i], ret);
			ret=1;
			if(lis<cache[i])
			{
				lis=cache[i];
				break;
			}
		}
	}
}

int main()
{
	int i, j;
	//int k;
	scanf("%d", &t);
	for(i=0; i<t; i++)
	{
		scanf("%d", &n);
		for(j=0; j<n; j++)
		{
			scanf("%d", &arr[j]);
			cache[j]=1;
		}
		max_num=arr[j-1];
		Lis();
		printf("%d\n", lis);

		//for(k=0; k<n; k++)
		//	printf("%d ", cache[k]);
		//printf("\n");

		lis=0;
	}
	return 0;
}

deneb2016 7년 전 1

코드가 문제의 요구사항과 조금 다른것 같습니다.

이 문제에서는 테스트 케이스가 하나만 들어오는데, 올려주신 코드는 테스트 케이스가 여러 개 들어오는 경우의 코드네요

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

문제

문제

출처

ICPC

최대증가부분수열 문제 질문입니다.

mushi 7년 전 0

deneb2016 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말