[백준] 11054 : 가장 긴 바이토닉 수열

입력되는 배열의 인덱스를 기준으로 앞에서는 가장 긴 오름차순 배열, 뒤에서는 거꾸로 시작하는 가장 긴 오름차순 배열을 합하면 되는 문제이다. 이때 하나가 겹치므로 -1 해줘야 함.

 

1등코드

메모리 : 13176 KB

시간 : 76 ms

코드길이 : 4653 B

 

내 코드

메모리 : 14556 KB

시간 : 152 ms

코드길이 : 1284 B

 

[상위권 코드]

class Main {

    public static void main(String[] args) throws Exception {

        int N = read();
        int[] arr = new int[N], lis = new int[N], tmp = new int[N];

        int k, l = 0;
        for (int i = 0; i < N; i++) {

            arr[i] = read();

            if ((k = binarySearch(lis, 0, l - 1, arr[i])) == l) l++;
            lis[k] = arr[i];

            tmp[i] = l;

        }

        int max = l = 0;
        for (int i = N - 1; i >= 0; i--) {

            if ((k = binarySearch(lis, 0, l - 1, arr[i])) == l) l++;
            lis[k] = arr[i];

            if (max < l + tmp[i]) max = l + tmp[i];

        }

        System.out.print(max - 1);

    }

    private static int binarySearch(int[] a, int l, int r, int v) {

        int m;

        while (l <= r)
            if (a[m = l + r >> 1] < v) l = m + 1;
            else r = m - 1;

        return l;

    }

    private static int read() throws Exception {

        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;

    }

}

[내 코드]

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] DP_up = new int[N];
		int[] DP_down = new int[N];
		int[] DP_upDown = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
			DP_up[n] = 1;
			DP_down[n] = 1;
		}
		
		for(int i = 1; i < N; i++) {
			int plus_up = 0;
			int plus_down = 0;
			for(int j = 0; j < i; j++) {
				if(arr[i] > arr[j] && DP_up[j] > plus_up) //가장 긴 증가하는 부분수열
					plus_up = DP_up[j];
				
				if(arr[(N - 1) - i] > arr[(N - 1) - j] && DP_down[(N - 1) - j] > plus_down) //거꾸로 시작하는 가장 긴 증가하는 부분수열
					plus_down = DP_down[(N - 1) - j];
			}
			DP_up[i] += plus_up;
			DP_down[(N - 1) - i] += plus_down;
		}
		
		int result = 1;
		for(int n = 0; n < N; n++) {
			DP_upDown[n] = DP_up[n] + DP_down[n] - 1; // 둘을 합한 후 -1을 해준다
			if(DP_upDown[n] > result)
				result = DP_upDown[n];
		}

		sb.append(result);
		System.out.println(sb);
	}

}