[문제해결을 위한 창의적 알고리즘] 전깃줄 (고급, 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;

}

}

Big O(n^2): n은 입력 크기 (n개의 입력에 대해 lg sum을 해야 해야 하므로)

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/PowerLineSol259.java

문제해결을 위한 창의적 알고리즘 목록

출처: 한국정보올림피아드 (2007 지역본선 중고등부)

Sample Input

8

1 8

3 9

2 2

4 1

6 4

10 10

9 7

7 6

Sample Output

3