[문제해결을 위한 창의적 알고리즘] 전깃줄 (고급, p249)
이 문제도 풀이가 바로 떠오르지 않을 것 같은 문제이다. 문제에서는 교차하는 전깃줄을 없애는 방법으로 A(왼쪽) 전봇대 위치를 정렬하고난 후, B(오른쪽) 전봇대 위치의 숫자로 만들 수 있는 오름차순 순열의 최대 길이를 구하는 문제로 일단 변경시켰다. 그 다음 IDT (인덱스 트리)를 이용하여, B 전봇대의 값을 차례로 읽으면서 나보다 작은 값들이 몇개 있나를 업데이트 해 나간다. 모든 값을 읽은 다음 제일 윗 칸 즉, IDT 행렬의 첫번째 값이 오름 차순 순열을 만들 수 있는 최대 길이 값이 되고, 전체 입력 개수에서 최대 길이 값 만큼을 뺀 숫자가 결국 없애야 하는 전깃줄의 숫자가 된다는 풀이 내용이다.
풀이에서는 sort (정렬)을 위해 라이브러리를 사용하고 있으나, 여기서는 알고리즘을 배우는 사람이라면 한번쯤은 구현해 보아야 할 merge sort를 이용해 보았다. (참고)
import java.util.Scanner;
public class PowerLineSol259 {
// 전봇대 정보 저장을 위한 inner class 사용
static class W{
public int a = 0;
public int b = 0;
}
// 정보를 저장하기 위한 배열
public static W[] d = new W[100001];
// merge sort에 사용하기 위한 배열
public static W[] h = new W[100001];
// IDT를 위한 배열
public static int[] IDT = new int[1<<22];
// IDT를 업데이트 하는 메소드
public static void update(int n){
while(n>1){
if(IDT[n]>IDT[n/2])
IDT[n/2]=IDT[n];
n>>=1;
}
}
public static int max(int a, int b){
return a > b ? a : b;
}
// lg sum 함수
public static int lg_sum(int s, int e){
int m = 0;
while(s < e){
m=max(m, IDT[e]);
if((e%2)==0)
e--;
e>>=1;
s>>=1;
}
if (s==e)
m=max(m, IDT[s]);
return m;
}
// merge sort 함수
public static void mergesort(int low, int high){
if (low < high){
int middle = low +(high-low)/2;
mergesort(low, middle);
mergesort(middle+1, high);
merge(low, middle, high);
}
return;
}
// merge sort 함수
public static void merge(int low, int middle, int high){
for (int i = low; i <= high; i++)
h[i]=d[i];
int i = low;
int j = middle+1;
int k = low;
while(i<=middle && j <= high){
if (h[i].a<=h[j].a){
d[k]=h[i];
i++;
}
else{
d[k]=h[j];
j++;
}
k++;
}
while(i<=middle){
d[k]=h[i];
k++;
i++;
}
return;
}
public static void main(String[] args) {
int i, base, n, m=-1;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (i = 1; i<=n; i++){
d[i]= new W();
d[i].a = sc.nextInt();
d[i].b = sc.nextInt();
if (m < d[i].b)
m = d[i].b;
}
sc.close();
mergesort(1,8);
for (base =1; base<m; base<<=1);
for (i=1; i<=n; i++){
IDT[base+d[i].b-1]=lg_sum(base,base+d[i].b-2)+1;
update(base+d[i].b-1);
}
System.out.println(n-IDT[1]);
return;
}
}
출처: 한국정보올림피아드 (2007 지역본선 중고등부)
Sample Input
8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6
Sample Output
3