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

 

문제

문제 링크 : https://www.acmicpc.net/problem/11054

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	21026	10969	8694	52.019%

문제

수열 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의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

풀이

처음에는 축을 계속 바꿔가면서 해보려고 했지만, 생각보다 어려웠다.

단순하게 우선 생각한 방법은 다음과 같다.

1. 모든 노드에 대해 본인 기준 왼쪽 수열 + 오른쪽 수열이 최대인 노드를 찾아야 한다.
2. 왼(오른)쪽 수열은 그냥 해당 노드 기준 왼(오른)쪽으로 진행하며 일일히 찾는다.

이때 시간복잡도는 대략 $n(n+1)/2 + n(n+1)/2 + n = O(n^2)$ 정도이기 때문에 충분히 가능하다고 생각했다.

 

코드

import java.io.IOException;

public class Main {
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        //input
        int n = Integer.parseInt(br.readLine());     
        String[] spl = br.readLine().split(" ");

        int[] list = new int[n];
        for(int i=0; i<n; i++) {
            list[i] = Integer.parseInt(spl[i]);
        }

        //logic
        /*n(n+1) + n -> 1,001,000 */
        int[] leftlist = new int[n];
        int[] rightlist = new int[n];

        //left
        for(int i=0; i<n; i++) {
            for(int j=i; j>=0; j--) {
                if(list[i] > list[j]) {
                    leftlist[i] = Math.max(leftlist[i], leftlist[j]+1);
                }
            }
        }
        //right
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if(list[i] > list[j]) {
                    rightlist[i] = Math.max(rightlist[i], rightlist[j]+1);
                }
            }
        }

        //output
        int answer = 0;
        for(int i=0; i<n; i++) {
            answer = Math.max(leftlist[i]+rightlist[i], answer);
        }
        System.out.println(answer+1);
    }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!