[백준 *Java] - 가장 긴 바이토닉 부분 수열 (11054)

 

가장 긴 바이토닉 부분 수열 문제보기

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

문제 설명
수열 S가 어떤 수 S(k)를 기준으로 S1 < S2 < ....S(k-1) < S(k) > S(k+1) > S(n-1) > S(n) 을 만족한다면,
그 수열을 바이토닉 수열이라고 한다.
예를 들어,
{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} 은 바이토닉 수열이 아니다.

---

👇  접근방식

생각한 로직은,
먼저 수열 전체를 가장 긴 증가하는 수열 길이를 찾은 뒤,
가장 긴 수열의 마지막 위치에있는 인덱스 값을 찾은 뒤, 
그 기점으로 긴 감소하는 수열을 찾아서 붙혀주는 방식으로 코드를 짤 생각입니다.

하.. 역시 단순하진 않았습니다. 이렇게하면 가장 길다고 생각했지만, 오류가 있어서 다른 로직으로 설계를 해야합니다.

---

아래는 실패한 코드입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int [] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int target[] = new int[N + 1]; // 입력 받은 수열의 길이 +1
        DP = new int[N + 1];
        Arrays.fill(DP, 1); // 최소 배열은 길이가 1이니 전체 초기화

        for (int i = 1; i < target.length; i++) {
            target[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 2; i < DP.length; i++) {
            for (int j = 1; j < i; j++) {
                if (target[i] > target[j] && DP[j]+1 > DP[i]) {
                    DP[i] = DP[j] + 1;
                }
            }
        }

        int max = 0;
        int chk = 0;
        for (int i = 1; i < N; i++) {
            if (DP[i] > max) {
                max = DP[i];
                chk = i;
            }
        }


        for (int i = chk + 1 ; i < DP.length; i++) {
            for (int j = chk; j < i; j++) {
                if (target[j] > target[i] && DP[j] >= DP[i]) {
                    DP[i] = DP[j] + 1;
                }
            }
        }
        for (int n : DP) {
            if (n > max) max = n;
        }
        System.out.println(max);
    }
}

다른 접근으로 푼 풀이방식으로 설명드리겠습니다.

일단 테스트케이스를 가지고 설명하겠습니다.

다른 방법은, 처음에 풀 때와는 달리 왼쪽에서 오른쪽, 오른쪽에서 왼쪽 증가하는 수열을 각각 구해서 겹치는 수를 뺀 값을 바이토닉 최대 길이라고 생각을하고 만드는 코드 구현 설명입니다.

테스트 케이스 

{1, 5, 2, 1, 4, 3, 4, 5, 2, 1} 로 확인합니다.

	0	1	2	3	4	5	6	7	8	9
left to right ----->	1	1, 5	1, 2	1	1, 2, 4	1, 2, 3	1, 2, 3, 4	1, 2, 3, 4, 5	1, 2	1
right to left <-----	1	1, 2, 3, 4, 5	1, 2	1	1, 2, 3, 4	1, 2, 3	1, 2, 4	1, 2, 5	1, 2	1

위에 있는 표를 보면,

왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 증가하는 수열로 구현합니다.

그 이후, 두 배열을 합친 뒤, 겹치는 수 '5'를 즉 수 1을 빼면 바이토닉 최대값이 됩니다.

아래는 성공한 코드 입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int [] DP_leftToRight;
    static int [] DP_rightToLeft;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int target[] = new int[N + 1]; // 입력 받은 수열의 길이 +1
        DP_rightToLeft = new int[N + 1];
        DP_leftToRight = new int[N + 1];
        DP_leftToRight[1] = 1;
        DP_rightToLeft[N] = 1;
        for (int i = 1; i < target.length; i++) {
            target[i] = Integer.parseInt(st.nextToken());
        }


        for (int i = 2; i <= N; i++) {
            DP_leftToRight[i] = 1;
            for (int j = 1; j < i; j++) {
                if (target[i] > target[j]) {
                    DP_leftToRight[i] = Math.max(DP_leftToRight[j] + 1, DP_leftToRight[i]);
                }
            }
        }

        for (int i = N-1; i > 0; i--) {
            DP_rightToLeft[i] = 1;
            for (int j = N; j > i; j--) {
                if (target[i] > target[j]) {
                    DP_rightToLeft[i] = Math.max(DP_rightToLeft[j] + 1, DP_rightToLeft[i]);
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= N; i++) {
            int temp = DP_leftToRight[i] + DP_rightToLeft[i];
            //System.out.println(temp);
            if (temp > max) max = temp;
        }

       System.out.println(max-1);
    }
}