백준 11054 - 가장 긴 바이토닉 부분 수열

문제 링크입니다 https://www.acmicpc.net/problem/11054

 

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

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 합니다. 

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아닙니다.

이때 수열이 주어지면, 가장 긴 바이토닉 수열의 길이를 구하는 문제입니다.

 

어려워 보이는 문제이지만 나눠서 생각하면 쉽게 풀리는 문제입니다.

1

5

2

1

4

3

4

5

2

1

이라는 수열이 있다고 가정하겠습니다.

이때 가장 긴 바이토닉 수열은 1, 2, 3, 4, 5, 2, 1 로 길이가 7입니다. 

 

1 .→ 오른쪽으로 증가하는 수열

2. ← 왼쪽으로 증가하는 수열

의 길이를 찾은 다음 각각의 칸을 더해준다음 최댓값을 찾아주면 쉽게 풀립니다.

 

자세한 것은 코드를 참고해주세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int up[1001];
int down[1001];
int num;
int up_cnt[1001];
int down_cnt[1001];

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> num;
	for (int i = 1; i <= num; i++) {
		cin >> up[i];
		down[i] = up[i];
	}
	for (int i = 1; i <= num; i++) {
		up_cnt[i] = 1;
		for (int j = 1; j <= i; j++) {
			if (up[i] > up[j] && up_cnt[j] + 1 > up_cnt[i]) {
				up_cnt[i] = up_cnt[j] + 1;
			}
		}
	}
	for (int i = num; i >= 1; i--) {
		down_cnt[i] = 1;
		for (int j = num; j >= i; j--) {
			if (down[i] > down[j] && down_cnt[j] + 1 > down_cnt[i]) {
				down_cnt[i] = down_cnt[j] + 1;
			}
		}
	}
	int max_ = 0;
	for (int i = 1; i <= num; i++) {
		max_ = max(max_, up_cnt[i] + down_cnt[i]);
	}
	cout << max_ - 1;
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요