[C] 백준 - 11054번: 가장 긴 바이토닉 부분 수열

8월 21일(월) - 다이나믹 프로그래밍 (11054번)

11054번: 가장 긴 바이토닉 부분 수열

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- "11053번: 가장 긴 증가하는 부분 수열" 문제의 풀이에 더 추가하는 방향의 풀이를 예상

 

- 입력은 수열의 크기 N, 수열을 이루고있는 숫자들이 입력된다

- 11053번의 풀이에서는 증가하는 부분수열을 구했고, 11054번의 풀이에는 감소하는 부분수열을 추가하면 된다

- 증가하는 부분수열은 dp_left[ ], 감소하는 부분수열은 dp_right[ ]에 저장되어있기에

  for문을 돌리면서 ( dp_left[ ] + dp_right[ ] - 1 ) 값들 중에서 가장 큰 값을 변수 max에 갱신해준다

  (증가하는 부분수열의 최댓값과 감소하는 부분수열의 최댓값이 일치하기에 -1을 해주어야한다)

- 출력은 최종적으로 구한 max값을 출력한다

[C] 백준 - 11053번: 가장 긴 증가하는 부분수열

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

// 11054번 풀이

int arr[1001];
int dp_left[1001];
int dp_right[1001];

#include <stdio.h>

int MAX(int x, int y)
{
	return ((x > y) ? (x) : (y));
}

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

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &arr[i]);
	}

	// 11053번 풀이 그대로 -> 증가하는 부분수열 구하기
	dp_left[1] = 1;
	for (int i = 2; i <= N; i++)
	{
		dp_left[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (arr[i] > arr[j])
			{
				dp_left[i] = MAX(dp_left[i], dp_left[j] + 1);
			}
		}
	}

	// 감소하는 부분수열 구하기
	dp_right[N] = 1;
	for (int i = N - 1; i >= 1; i--)
	{
		dp_right[i] = 1;
		for (int j = N; j > i; j--)
		{
			if (arr[i] > arr[j])
			{
				dp_right[i] = MAX(dp_right[i], dp_right[j] + 1);
			}
		}
	}

	// 최대길이 구하기
	int max = 0;
	for (int i = 1; i <= N; i++)
	{
		int sum = dp_left[i] + dp_right[i] - 1;
		if (sum > max)
		{
			max = sum;
		}
	}

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ