✅ DP

문제

링크

1. 문제 접근 및 해결 로직

바이토닉 수열일 경우는 3가지다.
1. 주어진 수열이 오름차순 정렬되어 있는 경우 (주어진 수열 자체가 바이토닉 수열)
2. 주어진 수열이 내림차순 정렬되어 있는 경우 (주어진 수열 자체가 바이토닉 수열)
3. 이외의 경우 (바이토닉 수열을 직접 찾아야 함)

1, 2번 경우는 가장 긴 바이토닉 수열의 길이가 주어진 수열의 길이이므로 따로 탐색을 해줄 필요가 없다.
따라서 처음에 올림차순인지 내림차순인지 판별해보고 둘 다 아니라면
3번의 경우로, 바이토닉 수열을 직접 찾아야 한다.

3번의 경우의 특징은 중간에 바이토닉 수열의 기준이 되는 값이 있고 그 기준값보다 왼쪽 수들은 기준값에서부터 점점 감소하고 기준값보다 오른쪽 수들도 기준값에서부터 점점 감소하는 모양이라는 것이다.

따라서 기준이 되는 값을 $1<=n<=N-2$ 범위 내에서 반복문을 돌며 지정해주고 지정해준 각각의 경우마다 $n$ 왼쪽 수들은 $n$에서부터 감소하는 수열, 오른쪽 수들도 감소하는 수열로 나누어 세어주면된다.

• 정의
  $f_1(n)$ : $n$ 의 왼쪽 수들로 이루어진 수열에서 가장 긴 감소하는 수열의 길이 ($n$에서부터 왼쪽으로 이동하면서)
  $f_2(n)$ : $n$ 의 오른쪽 수들로 이루어진 수열에서 가장 긴 감소하는 수열의 길이 ($n$에서부터 오른쪽으로 이동)
• 구하는 답

1. $N$ : 주어진 수열이 오름차순 or 내림차순일 경우
2. $max(f_1(n)+f_2(n)-1),(1<=n<=N-2)$
   기준값이 중복해서 세어졌으므로 -1

• 초기값
  $dp_1(n)=1,(1<=n<=N-2)$
  $dp_2(n)=1,(1<=n<=N-2)$
• 점화식

1. $dp_1(i-1)=dp_1(i)+1,(arr[i-1]<arr[i]),(1<=i<=n)$
2. $dp_1(i-1)=dp_1(i),(arr[i-1]>=arr[i]),(1<=i<=n)$
3. $dp_2(i+1)=dp_2(i)+1,(arr[i+1]<arr[i]),(n<=i<=N-2)$
4. $dp_2(i+1)=dp_2(i),(arr[i+1]>=arr[i]),(n<=i<=N-2)$

• $f_1(n)=max(dp_1(0),dp_1(1),...,dp_1(n))$
• $f_2(n)=max(dp_2(n),dp_2(n+1),...,dp_2(N-1))$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항