[백준] DP - 11054번, 가장 긴 바이토닉 부분 수열 (다른 풀이 봄)
* 공부 목표
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
문) 수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
풀이
1. 처음 생각해서 망한 풀이
- k = Max 값 || SecondMax값
- k값 이전까지는 증가 부분 수열, k값 이후에는 감소 부분 수열
- k가 Max일 때와 SecondMax일 때 중 더 긴 쪽이 정답
예제에 나온 답 제외하고 다른 반례는 맞게 출력됐다.
어떤 부분이 문제였나?
수열 내 Max값이 2개 이상 있을 때 기준이 되는 k가 먼저 나온 값이 됨.
따라서 바이토닉 수열은 맞지만 <가장 긴 수열>은 아니므로 정답이 아니게 됨.
(사실 이게 아니더라도 너무 길고 재사용성 낮은 코드라 런타임 에러 떴을 확률이 높았음.)
2. 다른 풀이의 아이디어
- 오름차순 부분 수열, 내림차순 부분 수열을 각각 구한다.
- 두 개의 부분 수열을 합한다.
- 누적된 값(dp[i]) 중 최댓값을 구한다. ➡️ 결과
- 원소가 1개씩 중복되어 있으므로 결과에서 -1을 해줘야 정답
코드
import java.util.*;
import java.io.*;
public class Main {
static int n;
static int[] arr;
static int[] first;
static int[] after;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
first = new int[n];
after = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
first();
after();
//max 값 찾기
int max = 0;
for(int i=0; i<n; i++) {
max = (max < first[i] + after[i]) ? first[i] + after[i] : max;
} System.out.println(max - 1);
br.close();
}
public static void first() {
for(int i=0; i<n; i++) {
first[i] = 1;
for(int j=0; j<i; j++) {
if(arr[j] < arr[i] && first[i] < first[j] +1) first[i] = first[j] + 1;
}
}
}
public static void after() {
//시작이 뒤
for(int i=n-1; i >= 0; i--) {
after[i] = 1;
for(int j=n-1; j>=0; j--) {
if(arr[j] < arr[i] && after[i] < after[j] +1) after[i] = after[j] + 1;
}
}
}
}
각 수열을 따로 구해 더한다는 개념은 생각하지 못해서 충격이었다.🥹
머리 쥐어 싸매며 고민해도, 구상이 잘못되면 처음부터 새로 해야한다.
열심히... 더 많이... 배워야겠다.