바이토닉 수열은 세가지 경우가 있다.
- 증가하는 수열
- 감소하는 수열
- 증가하다가 감소하는 수열
이렇게 세가지 경우를 봤을 때 가장 긴 수열의 길이는 3번이다.
그러면 증가하다가 감소하는 수열은 어떻게 구할까?
일단 i 번째 수를 간단하게 i라고 하겠다.
그러면 처음부터 N까지의 수열 중 (i를 마지막 수로 하는 증가하는 수열) + (i를 시작으로하는 감소하는 수열)을 구하면 이것이 i를 반환점??으로 증가하다가 감소하는 수열인 것이다.
0 : 증가하는 수열의 길이
1 : 감소하는 수열의 길이
2 : 증가하다가 감소하는 수열의 길이이렇게 가정하면
dp[n][0] : n 번째 수를 마지막으로 증가하는 수열의 길이
dp[n][1] : n 번째 수를 처음으로 감소하는 수열의 길이
dp[n][2] : 증가하다가 n을 기준으로 감소하는 수열의 길이 라고 할 수 있으며
dp[n][2] = dp[n][0] + dp[n][1] - 1 인 것을 알 수 있다.
여기서 -1 의 역할은 n 번째 수의 길이 1 을 두 번 더한 것을 한번 빼준 것이다.
증가하는 수열의 길이는 [백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]을 풀어봤으면 쉽게 풀 수 있다.
다음으로 구할 부분은 i번째 수를 시작으로 감소하는 수열의 길이이다.
[백준] 11722번 : 가장 긴 감소하는 부분 수열 - JAVA [자바] 에서는 i 번째 수로 끝나는 가장 긴 감소하는 수열의 길이를 구했었다.
하지만 이 부분에서 다르게 생각하면 되게 쉽게 풀 수 있다.
역순으로 N 부터 i 번째 수까지 i 번째 수로 끝나는 증가하는 부분 수열의 길이를 구하면 된다.
즉 위의 증가하는 수열을 구한 방법을 역순으로 하면 된다는 것이다.
그러면 코드를 보면서 해결해보자
public class bj11054 {
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// 1. 증가하는 수열 2. 감소하는 수열 3. 증가하다가 감소하는 수열 들 중 가장 길이가 긴 수열은 3번이다.
// 증가하는 수열은 내 왼쪽을 보면서 구하고
// 감소하는 수열은 내 오른쪽을 보면서 구한다
// 그 후 i 번째 수를 기준으로 i 번째 전으로 가장 긴 증가하는 수열의 길이 + 후로 가장 긴 감소하는 수열의 길이
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 세 가지의 경우의 수에 따라 구할 수 있는 수열이 다르며 길이 또한 달라진다
// 0 : 증가하는 수열
// 1 : 감소하는 수열
// 2 : 증가하다가 감소하는 수열
// 각 숫자의 수열의 길이
int[][] dp = new int[N + 1][3];
// 가장 초기의 수열은 자기 자신이며 그 길이는 1이다.
for (int i = 1; i < N + 1; i++) {
dp[i][0] = 1;
dp[i][1] = 1;
dp[i][2] = 1;
}
// i 번째 수의 왼쪽을 보면서 증가하는 수열을 구한다.
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
// 그 전의 수열에 내가 붙어서 새로운 수열을 만들었을 때
// 그 수열의 길이가 지금 내 수열의 길이보다 길면
if (dp[i][0] < dp[j][0] + 1) {
dp[i][0] = dp[j][0] + 1;
}
}
}
}
// 감소하는 수열
// 오른쪽 끝인 N부터 시작하면 -> 증가하는 수열을 구하면 된다.
for (int i = N; i > 0; i--) {
// N부터 i 번째 수 다음까지
for (int j = N; j > i; j--) {
if (arr[j] < arr[i]) {
if (dp[j][1] + 1 > dp[i][1]) {
dp[i][1] = dp[j][1] + 1;
}
}
}
}
// 중복 제거
for (int i = 1; i < N + 1; i++) {
dp[i][2] = dp[i][0] + dp[i][1] - 1;
}
// 가장 긴 수열의 길이를 구한다
int answer = 0;
for (int i = 1; i < N + 1; i++) {
if (dp[i][2] > answer) {
answer = dp[i][2];
}
}
bw.write(answer + "\n");
bw.flush();
bw.close();
br.close();
}
}