문제
https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
풀이
전체 전깃줄 개수 - 전깃줄의 최장증가 수열 개수
= 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수
A 값의 순서로 B 값을 수열로 만들어보면 {8, 2, 9, 1, 4, 6, 7, 10} 이다. 이 수열의 최장증가수열의 개수를 구해서, 전체 전깃줄 개수에서 빼면 답을 구할 수 있다.입력이 정렬되어 들어오지 않기 때문에 A값 기준으로 정렬한 후, 이분 탐색 이용하여 LIS의 개수를 구한다.
LIS 알고리즘 참고
2021.11.04 - [Algorithm] - [Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)
[Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)
LIS 알고리즘이란? LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 풀이 1. DP로 풀기 시간 복잡도 O(N^2) 이
gom20.tistory.com
소스코드
package lis;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class BOJ2565 {
public static int[][] arr;
public static int[] temp;
public static int N;
public static void main(String[] args) throws Throwable {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N][2];
temp = new int[N];
StringTokenizer st = null;
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2){
return o1[0] - o2[0];
}
});
int idx = 0;
temp[idx] = arr[idx][1];
for(int i = 1; i < N; i++){
if(temp[idx] < arr[i][1]){
idx++;
temp[idx] = arr[i][1];
continue;
}
temp[lowerbound(0, idx, arr[i][1])] = arr[i][1];
}
System.out.println(N - (idx + 1)); //idx 0부터 데이터가 있으므로
}
public static int lowerbound(int L, int R, int num){
// temp배열에서 num의 lowerbound를 찾아서 index를 리턴
int mid = 0;
while(L < R){
mid = (L+R)/2;
if(num <= temp[mid]) R = mid;
else L = mid+1;
}
return R;
}
}
'💡Problem Solving > BOJ' 카테고리의 다른 글
[BOJ 13305] 주유소 (Java) (0) | 2021.11.11 |
---|---|
[BOJ1541] 잃어버린 괄호 (Java) (0) | 2021.11.10 |
[BOJ 9251] LCS 최장 공통 부분 수열 문제 (Java) (0) | 2021.11.08 |
[BOJ 2156] 포도주 시식 (Java) (0) | 2021.11.08 |
[BOJ 1932] 정수 삼각형 (Java) (0) | 2021.11.08 |