백준 18195번 정점 찾기

출처 : 나는코더다 2019 송년대회 K번

solved.ac 티어 : P2

 

링크

 

인터랙티브 문제다. 나 혼자 삽질해서 푼 문제기도 하다.

 

압도적 롱코딩 1등...

나는 이 문제의 풀이를 전개해나가는데 두 가지의 방식으로 쿼리를 사용할 것이다.

 

1. i번째 비트가 0인 정점끼리 모두 묶고, 1인 정점끼리도 모두 묶고 i번째 비트가 0인 정점과 1인 정점이 서로 연결되어있는지 확인한다. a와 b의 i번째 비트가 다른지 확인할 수 있다. 쿼리를 한 번 사용한다.

 

2. a와 b의 비트값이 다른 비트를 하나 알고 있고, 그 비트의 비트값도 알고 있을 때 사용할 수 있는 방식이다. 알고 있는 비트를 x번째 비트라 하고, 현재 알려고 하는 비트를 i번째 비트라 하자. 또 a는 x번째 비트가 0이고, b는 x번째 비트가 1이라 하자. 아니라면 swap하면 되므로 일반성을 잃지 않는다.

(x번째 비트와 i번째 비트가 0인 집합),(x번째 비트가 0이고 i번째 비트가 1인 집합),(x번째 비트가 1이고 i번째 비트가 0인 집합),(x번째 비트와 i번째 비트가 1인 집합)으로 정점들을 나눈다.

이 네 집합이 모두 서로 서로소임은 자명하다.

그리고 일단 같은 집합 내부에서는 모두 서로 간선을 추가해주자. 

그 다음 (x번째 비트와 i번째 비트가 0인 집합)에서 x번째 비트가 1인 집합 전체에 간선을 이어준다.

이때의 그래프를 그림으로 그리면 다음과 같다. (그림 실력 양해좀)

이때 a는 윗부분에, b는 아랫부분에 위치한다. 그리고 오른쪽 위 부분에 있는 수와 아래쪽 부분에 있는 수가 연결되어있는지 쿼리를 날려주자.

그렇다면 a가 오른쪽 위에 있다면 true, 아니면 false가 날아올 것이다.

이렇게 a의 i번째 비트값을 알아냈다.

b의 i번째 비트값까지 알아내는 방법은 1번방식으로 쿼리를 날려서 같다/다르다를 확인하면 된다.

 

그러면 이제 이 풀이를 어떻게 사용할까?

 

먼저 비트값이 다른 비트 하나를 찾아내야만 한다. 1번방식으로 쿼리를 날려줘서 확인할 수 있다. 여기서 비트값이 같은 비트를 찾아냈다면 손해 같지만 일단 넘어가자.

그러면 언젠가 비트값이 다른 비트를 찾을 수 있을 것이다. (a!=b이므로)

이제 이때 다른 비트들을 모두 순회하면서 2번방식으로 다 값을 찾아주면 된다. 그런데 비트값이 다른 비트를 찾느라고 이미 쿼리를 한 번 날린 비트에 대해서는, 비트값이 서로 같다는 것을 이미 알고 있다. 여기서는 쿼리를 하나 아낄 수 있다.

그러므로 비트마다 쿼리를 최대 두 번 사용하므로 총 2*7=14번만에 답을 찾을 수 있다.

하나 넘친다.

하지만 비트값이 다른 비트 하나를 딱 찾았을 때, a와 b의 비트값을 결정할 이유가 없다는 것을 알 수 있다. a에 0을 넣고 b에 1을 넣든, a에 1을 넣고 b에 0을 넣든, 전혀 상관이 없다.

그러므로 쿼리가 한 번 절약되어 13번만에 답을 찾을 수 있다.