글 읽기 - 이진 탐색을 썼는데... 시간 초과.,..

gkgkehdrms 2년 전 0

안녕하세요 앞서 이분 탐색 LIS2를 풀고

LIS3도 풀어보려고 왔으나, 동일한 포맷인데 시간 초과가 발생하고 있습니다.

딱히 문제가 될 건 없어보이는데... 어떤 부분 때문에 시간 초과가 발생하는지 팁 좀 주셨으면 합니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int* pa;
int* dp; //LIS 배열

//이진 탐색 진행
int Search(int ptr, int tg)
{
	int l = 0;
	int r = ptr - 1;
	int c;
	while (1)
	{
		c = (l + r) / 2;
		if (dp[c - 1] < tg && tg < dp[c]) break;
		if (dp[c] > tg) r = c - 1;
		else if (dp[c] < tg) l = c + 1;
		else break;
	}

	return c;
}


int main()
{
	int i, ptr, n;
	ptr = 0;
	scanf("%d", &n);
	pa = (int*)calloc(n, sizeof(int));
	dp = (int*)calloc(n, sizeof(int));
	for (i = 0; i < n; i++)
	{
		scanf("%d", &pa[i]);
	}

	for (i = 0; i < n; i++)
	{
		// 초기값 넣기
		if (i == 0)
		{
			dp[ptr] = pa[0];
			ptr++;
		}
		else
		{
			//2번째 값을 넣을 경우 빠르게 계산하기 위해
			if (ptr == 1 && pa[i] < dp[ptr - 1])
			{
				dp[ptr - 1] = pa[i];
			}
			//LIS 값의 끝보다 클 경우 이진 탐색 없이 추가
			else if (dp[ptr - 1] < pa[i])
			{
				dp[ptr] = pa[i];
				ptr++;
			}
			//LIS 끝 값보다 작으면 이진 탐색
			else
			{
				int temp = Search(ptr, pa[i]);
				dp[temp] = pa[i];
			}
		}
	}

	printf("%d", ptr);

	return 0;
}

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

문제

문제

출처

ICPC

이진 탐색을 썼는데... 시간 초과.,..

gkgkehdrms 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말