글 읽기 - 어디가 틀린지 찾아주실 고수분 계신가요..!

dsj 6년 전 0

lds-기준점-lis 로 생각해서 풀었는데 왜 틀렸다고 나오는 지 모르겠습니다..

#include<stdio.h>
int in[2002], lis[2002], dp[2002], lds[2002];
int bound_lis(int key, int last)
{
	int mid, fir = 1;
	while (fir < last)
	{
		mid = (fir + last) / 2;
		if (lds[mid] >= key)
			last = mid;
		else
			fir = mid + 1;
	}
	return last;
}
int bound_lds(int key, int last)
{
	int mid, fir = 1;
	while (fir < last)
	{
		mid = (fir + last) / 2;
		if (lds[mid] <= key)
			last = mid;
		else
			fir = mid + 1;
	}
	return last;
}
int main(void)
{
	int n, max = 1;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &in[i]);

	for (int i=0; i<n; i++)
	{
		int lisBegin = n, ldsBegin = n;
		int key = in[i];
		int a=0, b=0;

		//lis lds 첫 원소 구하기
		for (int ii = i + 1; ii < n; ii++)
		{
			if (key < in[ii])
			{
				lis[0] = in[ii];
				lisBegin = ii;
				break;
			}
		}
		for (int ii = i + 1; ii < n; ii++)
		{
			if (key > in[ii])
			{
				lds[0] = in[ii];
				ldsBegin = ii;
				break;
			}
		}
		//make lis
		for (int ii = lisBegin + 1; ii < n; ii++)
		{
			if (key < in[ii])	
			{
				if (lis[a] < in[ii])
				{
					lis[a + 1] = in[ii];
					a++;
				}
				else
					lis[bound_lis(in[ii], a)] = in[ii];
			}
		}
		//make lds
		for (int ii = ldsBegin + 1; ii < n; ii++)
		{
			if(key > in [ii])
			{
				if (lds[b] > in[ii])
				{
					lds[b + 1] = in[ii];
					b++;
				}
				else
					lds[bound_lds(in[ii], b)] = in[ii];
			}
		}
		//lis길이랑 lds길이
		int lenA = a + 1;
		int lenB = b + 1;

		//lis나 lds가 생성되지 않았으면 길이 0으로
		if (lisBegin == n) lenA = 0;
		if (ldsBegin == n) lenB = 0;

		//printf("%d: %d %d\n", i, lenA, lenB);
		//lis길이 + lds길이 + 기준점
		dp[i] = lenA + lenB + 1;
		if (max < dp[i])
			max = dp[i];
	}

	printf("%d", max);
	return 0;
}

chogahui05 6년 전 0

자잘한 처리가 문제인 거 같네요.

/*
10
1
2
3
9
6
7
13
21
4
8
output
7
your output
8
wrong answer

dsj 6년 전 0

틀린 부분을 수정하고 다시 제출했는데

100%까지 돌고 틀렸다고 나옵니다

어디가 틀린걸까요ㅓ ㅜ

#include<stdio.h>
int in[2003], lis[2003], dp[2003], lds[2003];
int bound_lis(int key, int last)
{
	int mid, fir = 0;
	while (fir < last)
	{
		mid = (fir + last) / 2;
		if (lis[mid] >= key)
			last = mid;
		else
			fir = mid + 1;
	}
	return last;
}
int bound_lds(int key, int last)
{
	int mid, fir = 0;
	while (fir < last)
	{
		mid = (fir + last) / 2;
		if (lds[mid] <= key)
			last = mid;
		else
			fir = mid + 1;
	}
	return last;
}
int main(void)
{
	int n, max = 1;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &in[i]);

	for (int i=0; i<n; i++)
	{
		int lisBegin = n, ldsBegin = n;
		int key = in[i];
		int a=0, b=0;

		//lis lds 첫 원소 구하기
		for (int ii = i + 1; ii < n; ii++)
		{
			if (key < in[ii])
			{
				lis[0] = in[ii];
				lisBegin = ii;
				break;
			}
		}
		for (int ii = i + 1; ii < n; ii++)
		{
			if (key > in[ii])
			{
				lds[0] = in[ii];
				ldsBegin = ii;
				break;
			}
		}
		//make lis
		for (int ii = lisBegin + 1; ii < n; ii++)
		{
			if (key < in[ii])	
			{
				if (lis[a] < in[ii])
				{
					lis[a + 1] = in[ii];
					a++;
				}
				else
					lis[bound_lis(in[ii], a)] = in[ii];
			}
		}
		//make lds
		for (int ii = ldsBegin + 1; ii < n; ii++)
		{
			if(key > in [ii])
			{
				if (lds[b] > in[ii])
				{
					lds[b + 1] = in[ii];
					b++;
				}
				else
					lds[bound_lds(in[ii], b)] = in[ii];
			}
		}
		//lis길이랑 lds길이
		int lenA = a + 1;
		int lenB = b + 1;

		//lis나 lds가 생성되지 않았으면 길이 0으로
		if (lisBegin == n) lenA = 0;
		if (ldsBegin == n) lenB = 0;
		//printf("%d: %d %d\n", i, lenA, lenB);
		//lis길이 + lds길이 + 기준점
		dp[i] = lenA + lenB + 1;
		if (max < dp[i])
			max = dp[i];
	}

	printf("%d", max);
	return 0;
}

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

문제

문제

출처

ICPC

어디가 틀린지 찾아주실 고수분 계신가요..!

dsj 6년 전 0

chogahui05 6년 전 0

dsj 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말