[Baekjoon/백준] 11054번: 가장 긴 바이토닉 부분 수열(C/C++)

단계별로 풀어보기 15단계(동적 계획법 1) 12번 문제

https://www.acmicpc.net/step/16

동적 계획법 1 단계

---

백준 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} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력: 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

힌트: 예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

---

접근 방법

이번 문제는 지난 시간에 풀었던 문제와 유사하게 수열 크기 N을 입력 받고, 수열을 구성하는 N개의 숫자를 입력해서 길이를 구하는 문제다. 다만 증가하는 부분 수열이 아닌 바이토닉 수열의 길이를 구해야한다. 바이토닉 수열은 내가 이해한 바로는 그냥 간단하게 말해서 숫자가 약간 언덕처럼 증가하다가 다시 감소하는 수열이다. 단, 수열 중간이나 끝에 값이 다시 증가해서는 안된다.

바이토닉 수열을 쉽게 생각해서 증가하는 수열 두개로 나눠서 보면 해결할 수 있다. 즉, 지난 포스트의 코드에서 약간 수정해서 최댓값 인덱스를 바로 나오지 않게 하고, 순서를 역순으로 검색을 추가해서 모든 계산이 끝난 뒤 이 둘을 합쳐 -1한 값(중간 최고점 값이 겹치므로)을 출력하기만 하면 문제를 해결할 수 있다.

---

코드

#include <stdio.h>
#define MAX 1001

int main(int argc, char *argv[]) {
	int N, max = 0, min, A[MAX], arr1[MAX], arr2[MAX];
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);

	for (int i = 0; i < N; i++) {
		min = 0;
		for (int j = 0; j < i; j++)
			if (A[i] > A[j] && arr1[j] > min)
				min = arr1[j];
		arr1[i] = min + 1;
	}

	for (int i = N - 1; i >= 0; i--) {
		min = 0;
		for (int j = N - 1; j >= i; j--)
			if (A[i] > A[j] && arr2[j] > min)
				min = arr2[j];
		arr2[i] = min + 1;
	}

	for (int i = 0; i < N; i++)
		if (arr1[i] + arr2[i] - 1 > max)
			max = arr1[i] + arr2[i] - 1;

	printf("%d\n", max);

	return 0;
}

---

결과

백준 제출 결과