BOJ#2352 반도체 설계

BOJ#2352 반도체 설계

* 문제

https://www.acmicpc.net/problem/2352

* 풀이

LIS 기본 문제입니다. 

LIS 설명

http://stack07142.tistory.com/56

비슷한 문제들

http://stack07142.tistory.com/102

http://stack07142.tistory.com/103

http://stack07142.tistory.com/287

* 나의 코드

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));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] A = new int[N];
        for (int i = 0; i < N; i++) A[i] = Integer.parseInt(st.nextToken());

        System.out.println(getLISLength(A, N));
    }

    static int getLISLength(int[] A, int N) {

        int lisLength;
        int[] tailTable = new int[N];

        tailTable[0] = A[0];
        lisLength = 1;

        for (int target = 1; target < N; target++) {

            if (A[target] < tailTable[0]) {

                tailTable[0] = A[target];
            } else if (A[target] > tailTable[lisLength - 1]) {

                tailTable[lisLength] = A[target];
                lisLength++;
            } else {

                int idx = Arrays.binarySearch(tailTable, 0, lisLength, A[target]);
                idx = idx < 0 ? -idx -1 : idx;

                tailTable[idx] = A[target];
            }
        }

        return lisLength;
    }
}