[Java] BOJ2352_반도체 설계

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

2352번: 반도체 설계

---

연결선이 겹치지 않기 위해서는 연결 포트의 번호가 증가하는 형태여야 한다.

이를 통해 최장 증가 부분 수열(LIS) 문제라는 것을 알 수 있다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
	static int[] arr;
	static int[] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		dp = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int index = 0;
		dp[0] = arr[0];
		for (int i = 1; i < N; i++) {
			if(arr[i] > dp[index]) dp[++index] = arr[i];
			else if(arr[i] < dp[index]) binarySearch(0, index, arr[i]);
		}
		
		System.out.println(index+1);
	}
	
	public static void binarySearch(int start, int end, int data) {
		int mid = (start+end)/2;
		if(start >= end) {
			if(dp[mid] < data) dp[mid+1] = data;
			else dp[mid] = data;
			return;
		}
		
		if(dp[mid] > data) {
			binarySearch(start, mid-1, data);
		} else if(dp[mid] < data) {
			binarySearch(mid+1, end, data);
		} else {
			return;
		}
	}
	
}