[백준 / BOJ] 11054 가장 긴 바이토닉 부분 수열

문제

출처 : www.acmicpc.net/problem/11054

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

수열S가 주어진다.

이때, 수열S의 어떤 수 A를 기준으로 A이전의 수가 증가하는 부분 수열 일때, A 이후가 감소하는 부분 수열 이라면, 그 수열을 바이토닉 수열 이라고 한다.

이때, 수열 S에서 가능한 모든 바이토닉 수열중 가장 긴 수열의 길이를 구하는 문제다.

 

풀이

N이 1000이므로 완전탐색으로 풀경우 시간초과가 난다.

다이나믹 프로그래밍으로 풀어야 하는 문제였다.

 

문제 이해가 좀 어려운 문제였다, 문제에서 묻는걸 쉽게? 쓰면,

수열 S의 부분 수열 중, 일정한 idx를 기준으로 증가하다 감소하는 가장 긴 부분 수열을 구하라는 문제다.

 

가장 긴 증가하는 부분 수열 문제를 응용해서 풀었다.

문제 : www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

풀이 : dlwnsdud205.tistory.com/127

[백준 / BOJ] 11053 가장 긴 증가하는 부분 수열

풀이가 상당히 간단한데, 그냥 앞에서부터 증가하는 최장 부분 수열을 찾고, 뒤에서 부터 증가하는 최장 부분 수열을 찾아주면된다.

 

구현은 위 풀이 링크와 똑같아서 간단히 설명하면,

현재 idx를 기준으로 1...idx 까지 반복하며 arr[i] < arr[idx]인 부분에 대해서만 dp최댓값을 갱신해주면된다.

예시) dp[idx] = max(dp[idx],dp[i]);

 

이를 앞, 뒤 똑같이 반복시켜준후, 앞에서 부터 증가하는 dp배열, 뒤에서 부터 증가하는 dp배열이 겹치는 부분에 대해서 최댓값을 찾아주면된다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11054%20%EA%B0%80%EC%9E%A5%20%EA%B8%B4%20%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4/main.cpp

devxb/JJUNalgo