글 읽기 - 증감수열을 찾을때 이렇게 해도 되는건가요?

mushi 5년 전 0

1 2 1 2 1 2 처럼 증가 후 감소나, 감소 후 증가 가 반복되는 수열 중 가장 긴 수열을 찾습니다.

가장긴 증가(혹은 감소)수열 찾는걸 조건을 넣어서 믹스시켰습니다만

아래와 같은 소스는 O(n^2) 인데, 다른 방법도 있을까요?

p.s 혹시 백준에 비슷한 문제 있을까요?

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

int num[1001];
int n;
int max = 1;

int solve() {

	int arr[1001];//길이 값

	int arr1[1001];//조건 값 
				   // 0 : 다음수가 뭐든 가능
				   //-1 : 다음수가 커야함 
				   //1 : 다음수가 작아야함

	arr[0] = 1;//처음이니까 길이 1
	arr1[0] = 0;//첫수는 항상 0

	for (int i = 1; i < n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (num[j] < num[i] && (arr1[j] == -1 || arr1[j] == 0) && max <= arr[j] + 1)
			{
				max = arr[j] + 1;
				arr[i] = max;
				arr1[i] = 1;
			}
			else if (num[j] > num[i] && (arr1[j] == 1 || arr1[j] == 0) && max <= arr[j] + 1)
			{
				max = arr[j] + 1;
				arr[i] = max;
				arr1[i] = -1;
			}
		}
	}


	/*

	for (int i = 0; i < n; i++)
	printf("%2d ", number[i]);
	printf("\n");
	for (int i = 0; i < n; i++)
	printf("%2d ", arr[i]);
	printf("\n");
	for (int i = 0; i < n; i++)
	printf("%2d ", arr1[i]);
	printf("\n");

	*/


	return max;
}

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}

	printf("%d\n", solve());
}

chogahui05 5년 전 1

증가 후 감소..

감소 후 증가.. 구간이 두 부분으로 쪼개진 건가요?

그 경우에는 증가 후 감소를 예로 들자면..

(1) 극점의 위치를 x라고 두시고

처음 ~ x까지의 최대 증가 수열 + x ~ 끝까지의 최대 감소 수열의 값 중

최대치를 찾으면 될 거 같은데요. 이 두 연산은 c++에 있는 upper_bound나 lower_bound를 이용하면 O(nlogn)에 끌날 수 있는 연산입니다.

1 2 4 5 6 3 2 4

같은 경우

x에서 끝까지의 최대 감소 수열은 어떻게 찾을까요?

이건 수열을 뒤집어서 생각하시면 됩니다.

4 2 3 6 5 4 2 1

뒤집어진 수열과 원래 수열을 어떻게 어떻게 mapping 시키면 될 거 같네요.

역방향인 경우에는 그냥 -1을 곱해가지고 하시면 됩니다.

mushi 5년 전 0

주어진 수열이 1 3 5 4 6 2 5 1 3 이면 1 3 2 5 3 (길이 5)의 지그재그 수열을 찾을 수 있습니다.

찾아보니 지그재그 라는 문제가 있더군요. 구간내 지그재그 숫자를 찾는거던데, 이것도 엄청 어려워 보이네요...(범위가 어마어마)

주어진 수열에서 가장긴 지그재그수열을 찾는 법중 빠른 해법이 있나요???

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

문제

문제

출처

ICPC

증감수열을 찾을때 이렇게 해도 되는건가요?

mushi 5년 전 0

chogahui05 5년 전 1

mushi 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말