[platinum1][해설안봄 알고리즘 분류 안봄] boj 26192 Greedy Drawers

아이디어성 문제로 특별한 알고리즘을 요구하진 않는다.

이런 문제의 특성상 풀때는 골머리를 앓지만 풀고나면 허탈할 정도로 간단하다..

 

노트북의 w(width),h(height), 각 노트북과 쌍이 되는 서랍의 w,h가 있고,  모든 노트북을 모든 서랍에 집어넣을 수 있게 하는 문제이다.

노트북을 돌려서 (w,h를 바꾸어) 집어넣을 수도 있기 때문에 서랍의 min(w,h)가 노트북의 min(w,h)보다 크고, 서랍의 max(w,h)또한 노트북의 max(w,h)보다 크면 넣을 수 있다.

w,h를 적절히 맞춘다면 노트북과 서랍은 밑의 그림처럼 나타낼 수 있다.

 

 Janko는 이 노트북과 서랍의 쌍을 적절히 맞추기 위해 다음 알고리즘을 사용하려고 한다. 각 노트북 또는 서랍이 선택할 수 있는 선택지의 갯수(노트북2는 서랍2, 서랍3으로 선택지가 2개, 서랍 7는 노트북5, 노트북9, 노트북 10으로 3개) 가 최소인 노트북or서랍을 골라서 (최소인 게 여러개이면 랜덤으로 하나를 선택해서) 그 선택지중 아무거나와 쌍을 이루게 한다. 이런 식으로 모든 노트북 과 서랍이 쌍을 이룰 때까지 반복한다.

 

여기서는 노1-서1 노2-서2 노3-서3 노4-서4 순으로 짝이 될 수 있을 것이다.

 

 

 나는 이런 밑의 그림과 같은 쌍이 적용되는 문제들을 예전에 훑어봤을 때는 janko와 똑같이 생각하였고, greedy하게 선택지가 최솟값인 항목을 (여러개이면 랜덤하게) 선택해서 쌍을 이루면 당연히 되는 줄 알았다. 

근데 예외가 있었다는것에 흥미를 느끼며 골머리를 싸매게 되었다 ... 

 

 이 문제는 janko의 알고리즘에 문제를 찾기 위해 예외인, 즉 janko의 방법대로 풀지않아도 모든 쌍을 이루게 만들 수 있는 예시가 있으면서, janko의 알고리즘대로 풀었을 때 확률 적으로 실패를 할 수도 있는 경우를 찾는 것이다.

janko의 알고리즘이 실패한 경우는 다음같은 경우이다.

 

 

 

각자 선택지가 하나밖에 없고 하나의 쌍을 이루면 나머지의 노드들은 더이상 쌍을 이룰 수 없을 때이다.

직접 해보면 아시겠지만, 무지성으로 테스트 케이스를 만들고 janko의 방법대로 푼다면 거의 반드시 풀린다는 걸 알 수 있다.(애초에 janko의 알고리즘 없이 해도 모든 쌍을 이룰 수 없는 경우 제외) 풀리지 않는 테스트 케이스를 발견한다면 이 문제를 거의 푼거랑 다름이 없다고 생각한다.

 

 오랜 시간 고민한 결과 다음과 같은 케이스에서 예외가 있다는 것을 발견했다.

 

노란 사각형 안은 빨간 동그라미 노드를 제외하면 고립되었다고 볼 수 있고, 따라서 빨간 노드를 저 노란 사각형 안과 매칭시키면  노란사각형안의 노드들은 일부만 쌍을 만들 수 있게 된다.

 

만약 이렇게 이루어져 있다면 최소 선택지가 1인 부분 부터 채워져 결국 노란 사각형안도 쌍이 다 만들어질 것이므로...

초록 사각형 처럼 선택지의 최소를 2로 맞춰줘야 한다!

 

결국 이런식으로 하면 될 것이라고 생각했고,  답을 제출했다.

결과는 실패였다.

 진행 도가 7 % 정도인가 까지 가서 실패했길래 작동에 오류가 있어서는 아니고, 왜 실패했는지 생각해보니 테스트 케이스 20개에서 랜덤하게 돌렸을 때 모든 테스트 케이스가 통과해야 정답으로 인정된다고 하는 것에서 감이 왔다.

저기서 janko가 틀림을 증명할 수 있는 케이스는 빨간 원 부분을 노란 사각형 과 연결시키는 것이다. 그런데 선택지의 개수는 2개인데 2개인 경우의 노드는 매우 많다... 노란, 초록 사각형을 제외한 모든 노드들은 선택지가 2개이다. 따라서 확률적으로 빨간원을 선택할 경우의 수는 N이 300이라 쳤을 때   1 /(600 - 2) 이다... 빨간 노드를 제외한 노드를 선택하면 

밑처럼 순차적으로 쌍이 이루어지기 때문이다.

 

그래서 확률을 높이기 위해서는 다른 방법을 써야 한다.

 

다른 방법이 많이 있을 수 있겠지만 내가 생각한 방법은 노란,초록 부분을 잇는 부분을 최소화 하면 10개의 노드를 최소 단위로 만들 수 있는데 ,  이 단위를 독립적으로 여러개 만드는 것이다.

 

이런식으로 만들면 하나의 단위 당 빨간 노드를 선택할 확률은 각 단위당  1/ (10 - 2) 이다. N 이 300이라고 하면 30개의 단위를 만들 수 있다. 여기서 각 단위는 독립적이기 때문에 하나의 단위에서 빨간노드를 뽑는데 실패하더라도 다른 노드에서 뽑으면 된다

모든 노트에서 빨간노드를 한번이라도 뽑을 확률은 여집합의 확률로 계산하면 1 - (7/8)^30  이고, 거의 1에 근접하는 수다. 

N은 150부터이므로   아무리 확률이 낮아도 1-(7/8)^15 이다.   (7/8 은 하나의 단위에서 빨간노드가 아닌 다른 노드를 뽑을 확률) 

결국 저런 식으로 문제를 푼다면 로또 맞을 확률이 아닌 이상 대부분 정답으로 인정되게 될 것이다.

만약 N이 5로 나눴을 때 나누어 떨어지지 않는다면, 예를들어 152이면 29개는 기존의 유닛으로 만들고 나머지 1개는 아래

처럼 네모의 중간부분을 길게 만들면 될 것이다.

 

저 그림을 실제 숫자로 만들어 넣는 부분은 조금 생각하면 될 문제이므로 생략한다.

 

사실상  시간복잡도는 거의 O(N)으로 봐도 될 거 같지만 귀찮아서 최적화는 하지 않았다...

package boj26192;

 

import java.util.Scanner;

 

public class Main {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int N = scan.nextInt();

int batch = N / 5 - 1;

 

StringBuilder sb = new StringBuilder();

 

 

for(int i = 0; i < batch ; i++) {

 

sb.append((300 - 4*i) + " " + (700 + 4*i) + "\n" );

sb.append((300 - 4*i) + " " + (700 + 4*i) + "\n" );

sb.append((299 - 4*i) + " " + (701 + 4*i) + "\n" );

sb.append((298 - 4*i) + " " + (702 + 4*i) + "\n" );

sb.append((297 - 4*i) + " " + (703 + 4*i) + "\n" );

 

}

 

int remain = N - 5 * batch;

int a = 300 - 4* batch;

int b = 700 + 4* batch;

sb.append((a) + " " + (b) + "\n" );

sb.append((a) + " " + (b) + "\n" );

 

for(int i = 3; i <= remain ; i++) {

sb.append((a+ 2 - i) + " " + (b - 2 + i) + "\n" );

}

 

 

 

sb.append("\n");

for(int i = 0; i < batch ; i++) {

 

sb.append((300 - 4*i) + " " + (701 + 4*i) + "\n" );

sb.append((300 - 4*i) + " " + (700 + 4*i) + "\n" );

sb.append((299 - 4*i) + " " + (702 + 4*i) + "\n" );

sb.append((298 - 4*i) + " " + (703 + 4*i) + "\n" );

sb.append((298 - 4*i) + " " + (703 + 4*i) + "\n" );

 

}

 

 

sb.append((a) + " " + (b + 1) + "\n" );

sb.append((a) + " " + (b) + "\n" );

 

for(int i = 3; i <= remain - 1 ; i++) {

sb.append((a+ 2 - i) + " " + (b - 1 + i) + "\n" );

}

sb.append((a+ 2 - (remain - 1)) + " " + (b - 1 + (remain - 1)) + "\n" );

 

 

 

System.out.println(sb);

 

 

}

 

 

}