RUN@KAIST 8/13 방학 연습 풀이

1. 전구

편의상 왼쪽 스위치와 오른쪽 전구의 번호가 1 2 3 4.. 처럼 순서대로 되어 있다고 하자. p[i] = (왼쪽 i번 스위치를 눌렀을 때 켜진 오른쪽 전구의 번호) 라 하자. 전선이 교차하지 않게 왼쪽에서 {i1, i2, i3, ... ik} 스위치를 켰다는 것은, p[i1] < p[i2] < p[i3] < ... < p[ik] 라는 것과 동치이다. 이렇게 최대 개수의 스위치를 켜는 것은, 최장 증가 부분 수열 (LIS) 문제와 동일하다. 이는 동적 계획법으로 O(N^2)에 찾고 역추적도 할 수 있다. (만약 방법을 모른다면, dp[i] = i번 수에서 끝나는 최대 길이의 LIS라 정의하고 생각해 보자.)

왼쪽 스위치와 오른쪽 전구의 번호가 실제로 1 2 3 4가 아니라는 것이 문제인데, 그냥 정렬한 후 배열 몇개씩 더 잡아서, i번 스위치의 실제 번호, i번 전구의 실제 번호 같은 걸 저장해 두면 된다. 

2. 부서 배치

문제를 요약하자면, 두 개의 부서가 있고, 같은 부서에 있기를 희망하는 관계와 다른 부서에 있기를 희망하는 관계가 있을 때, 모든 관계를 만족시키면서 두 부서 인원 차를 최소화해야 한다. 최소화를 하기 전에, 먼저 모든 관계를 어떻게든 만족시킬 수 있는지 살펴보자.

일단 다른 부서에 있기를 희망하는 관계만 존재한다면 이 문제는 잘 알려진 "이분 그래프" 판별 문제이다. 각 연결 컴포넌트에 대해서, 하나의 정점의 부서가 결정되면, 그에 인접한 정점의 부서가 결정되고, 또 다른 정점의 부서가 결정되고... 이것을 반복했을 때 어떠한 정점이 A / B 부서에 모두 존재해야 한다는 식의 모순이 생기면 (이는 홀수 사이클의 존재 여부와 동치이기도 하다) 이분 그래프가 아닌 것이고, 아닐 경우 이분 그래프임을 알 수 있다. 같은 부서에 있기를 희망하는 관계가 추가된다고 하여도 문제가 크게 달라지지 않는다. 여전히 하나의 정점의 부서가 결정되었을 때 그에 인접한 정점의 부서가 결정된다. 컴포넌트마다 깊이 우선 탐색을 해서 모순이 있는지 없는지를 체크해주면 문제가 해결된다.

이를 통해서 답이 -1인지 아닌지는 판별할 수 있다. 이제 최소화를 해야 하는데, 앞 알고리즘을 조금만 응용하면 쉽게 할 수 있다. 각 연결 컴포넌트에 대해서, 하나의 정점의 부서를 A로 결정하면 나머지 정점의 부서가 모두 유일하게 결정된다. 반대로 하나의 정점의 부서를 B로 결정하면 나머지 정점의 부서가 모두 반대가 되어서 역시 유일하게 결정된다. 즉, 한 정점의 부서를 A라고 결정했을 때 A부서에 Ca, B부서에 Cb개의 정점이 있다면, 가능한 정점 수의 경우의 수는 (Ca, Cb) 혹은 (Cb, Ca) 의 형태이다. 

우리는 각 컴포넌트에 대해서 A 부서에 Ca명이나 Cb명을 넣을 수 있다는 사실을 모두 구했다. 여기에 일반적인 knapsack DP 알고리즘을 사용하면 A 부서의 인원수로 가능한 수를 모두 알 수 있다. A 부서의 인원수를 알면 B 부서의 인원수가 당연히 결정된다. 고로 가능한 수 중 차이를 최소화하는 수를 찾아 반환한다. 시간 복잡도는 O(N^2)이다. 

3. 트리 분할

예전 연습 검역소와 비슷한 느낌의 그리디 알고리즘을 사용한다. (DP라 할 수도 있겠다.) 정점 v의 자식 서브트리에서 적당히 문제를 해결하면, 정점 v에서는 자식에서 올라온 path를 적절히 합쳐줘서 자신의 부모로 보낼 path를 정하고, 이를 리프에서 루트까지 계속 반복하면서 답을 구하는 알고리즘이다.

v의 자식 w에서 적절히 path를 묶었다면, 결과적으로 A개의 path가 묶이고, 자식이 부모로 길이 B의 path를 보내는 상황이 될 것이다. A를 최소화하는 게 일차적인 목표고, 그것이 같을 경우에는 자식이 보내준 길이 B가 작을 수록 좋으니, 각 노드마다 pair (A, B)를 최소화하는 것을 목표로 하자. (증명은 귀류법으로 하면 된다. 저것을 최소화하지 않고서 optimal한 답보다 좋은 답을 구할 수 없다.)

어떠한 노드 v에 대해서 문제를 해결할 때, 우리는 자식 노드들의 (A, B) pair를 모두 알 수 있다. 이를 처리하는 방법은 두 가지이다.

 * 1. 이 중 한 자식 노드의 path를 그대로 올려준다. 이 때 묶이는 path의 개수(A)는 고정된다. 단지 자식 path의 B 값에 따라서 현재 노드의 B 값이 작아질 뿐이다. 고로 올려주는 path는 자식 노드 중 B 값이 가장 작은 path일 것이다.

 * 2. 두 자식을 합쳐주고 path를 올려주지 않는다. 이 때 올려주는 path는 없다. 고로 B는 고정된다. 합쳐주는 두 path의 길이 합이 K를 넘느냐 아니느냐에 따라서 A가 변할 수 있다. 길이 합이 K가 넘지 않는 쌍을 찾기 위해서는, 자식 중 B가 작은 두 path를 찾아서 묶어주는 것이 좋다. 

이 두 선택지 중 (A, B)를 최소화하는 선택지를 고르면 된다. B가 K를 넘을 때마다 path를 잘라 줘야 함에 유의하자. 시간 복잡도는 O(n)인데, 정렬을 써서 O(nlgn)으로 구현하면 편하다.

4. 배수

우리가 해야 할 것은 일단 가능한 서로 다른 자리수의 등장 횟수를 최소화하고, 그 다음에 값을 최소화하는 것이다. 서로 다른 자리수라는 개념은 다루기 복잡해 보이니, 등장할 자리수의 부분집합을 고정시켜 놓고 (총 2^10 - 1의 경우의 수가 있을 것이다) 해당 자리수로 만들 수 있는 최솟값이 무엇인지를 알아보는 식으로 접근해보자.

이제 우리가 풀어야 하는 문제는 다음과 같다.

10개의 한자리 정수 중 k개의 정수 a_1, a_2 ... a_k 를 사용할 수 있다. 이 정수들을 사용해서 만들 수 있는 양의 N의 배수 중 최소를 구하여라.

쉽지 않아 보이는 문제인데, 재미있게도 완전 탐색으로 접근하면 실마리가 나온다. 예를 들어 가능한 정수가 {3, 4, 7} 이라고 하자. 가능한 후보들을 나열하면 3, 4, 7, 33, 34, 37, 43, 44, 47, 73, 74, 77, 333 ... 과 같이 나올 것이다. 만약에 초기에 3, 4, 7을 큐에 넣은 후, 큐에서 X가 나왔을 때, X가 N의 배수면 종료하고, 아니면 10X + 3, 10X + 4, 10X + 7을 큐에 넣는 식으로 완전 탐색을 반복하면 가능한 후보들을 크기 순으로 전부 나열할 수 있다.

이 방법은 완전 탐색이니 시간 안에 나오지도 않고, 큰 수 처리를 해야 한다는 불편함도 있지만, 사실 꽤 간단한 방법으로 시간 복잡도 O(Nk)를 유도할 수 있다. 아이디어는, N으로 나눈 나머지가 같은 수를 두 개 이상 고려할 필요가 없다는 것이다. 결국 0 mod N을 만족하는 최소의 양의 정수를 찾는게 우리의 문제이니, x mod N을 만족하는 수가 여럿 있으면 그 중 값이 가장 작은 것만 중요하고, 나머지는 답의 중간 과정을 이룰 수 없음을 쉽게 알 수 있다. N의 나머지로 visited 배열을 잡으면 결국 사전순 최소 최단 경로를 찾는 문제와 동일함을 알 수 있고, 간단한 너비 우선 탐색으로 O(Nk) 에 문제를 해결할 수 있다. 실제 답은 경로 역추적으로 구할 수 있다.

거진 문제를 푼 것 같지만, 애석하게도 이 풀이는 간당간당하게 시간 제한을 초과한다. O(2^10 * 10 * N)의 시간 복잡도를 가지고 3억을 약간 웃돌기 때문이다. 이를 최적화하기 위해서는 또 하나의 아이디어가 필요하다. 바로 2개의 숫자만으로 항상 답을 찾을 수 있다는 것이다. 

증명은 다음과 같다. S = {1, 11, 111, 1111, 11111, .... } 과 같은 무한집합을 생각해 보자. 비둘기집의 원리에 의해서 두 서로 다른 수가 같은 modulo를 가지는 경우가 존재할 것이다. 그 두 수의 차는 111111...000000... 과 같은 꼴을 이룰 것이고, N으로 나눈 나머지가 0이다. 고로 2개의 숫자만을 사용하는 답은 존재하고, 이는 3개 이상의 숫자를 가지는 부분 집합을 고려할 필요가 없다는 것을 뜻한다. 이 간단하고 흥미로운 증명을 통해서 시간 복잡도는 O(10^2 * N)으로 줄어들게 되고, 문제를 해결할 수 있다. 

설명이 이해가 안 될 수 있으니 같은 내용의 다른 풀이를 링크한다 : http://blog.naver.com/jh05013/221073686748