https://www.acmicpc.net/problem/2352
2352번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주
www.acmicpc.net
분류 : 다이나믹 프로그래밍 , 그리디 알고리즘 , LIS
더보기
import java.io.*;
import java.util.*;
public class Main {
static Myscanner sc = new Myscanner();
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static void main(String[] args) {
int N = sc.nextInt();
int[] list = new int[N];
int[] lis = new int[N];
for(int i=0;i<N;i++)
{
int e = sc.nextInt();
list[i] = e;
}
lis[0] = list[0];
int len = 1;
for(int i=1;i<N;i++)
{
if(list[i]<lis[0]){
lis[0] = list[i];
}
else if(list[i]>lis[len-1]){
lis[len++] = list[i];
}
else{
int index =Arrays.binarySearch(lis, 0,len,list[i]);
index = index<0 ? -index-1 : index;
lis[index]= list[i];
}
}
out.println(len);
out.flush();
}
}
class Myscanner {
BufferedReader br;
StringTokenizer st;
Myscanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str += br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
N개의 포트와 반대쪽의 N개의 포트를 연결할 때 서로 꼬이지 않게 연결하는 해서 최대 몇 개 까지 연결할 수 있는지 구하는 문제이다.
전형적인 LIS 문제로써 N의 크기가 최대 40,000이므로 LCS (O(N^2)) 방법을 사용할 경우 시간 초과가 나게 되므로
(BinarySearch+dp) (O(N logN))를 사용하여 풀어야 한다.
내가 풀어온 LIS 문제 순서.
1. 1965번 : 상자 넣기 https://www.acmicpc.net/problem/1965
2. 2565번 : 전깃줄 https://www.acmicpc.net/problem/2565
3. 1365번 : 꼬인 전깃줄 https://www.acmicpc.net/problem/1365
'PS' 카테고리의 다른 글
[BOJ]5052번 : 전화번호 목록 (0) | 2017.04.24 |
---|---|
[BOJ]8983번 : 사냥꾼 (0) | 2017.04.22 |
[BOJ]1890번 : 점프 (0) | 2017.04.20 |
[BOJ]1620번: 나는야 포켓몬 마스터 이다솜 (0) | 2017.04.19 |
[BOJ]1874번 : 스택 수열 (0) | 2017.04.17 |