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

1. 도어맨

굉장히 간단한 O(N) 그리디 풀이도 있는 거 같은데 난 잘 모르겠어서 DP로 해결했다. DP[i] = (1 ~ i번 사람이 모두 럽에 들어갔을 때 더 넣을 수 있는 사람의 수) 라고 정의하자. 두가지 케이스가 있다.

 * 첫번째 사람을 클럽에 영영 안 넣고 두번째 사람부터만 계속 추가. 이 방법으로 K명이 추가로 들어갔다면 DP[i] = K가 가능해진다. 

 * 두번째 사람 이후를 K번 정도 더 넣고, 첫번째 사람을 추가. 차이에 문제가 생기지 않는다면 DP[i] = DP[i + K + 1] + K + 1가 가능해 진다. 

모든 K에 대해서 대충 시뮬레이션한 후, 시뮬레이션 과정에서 문제가 없었으면 값을 갱신해주면 된다. 이런 식으로 DP 테이블을 채우면 DP[0]이 답이 된다. 잘 구현하면 O(N^2) 정도에 할 수 있으며, 실제로는 O(N^3) 정도에 구현해도 입력이 작아서 시간 안에 잘 나온다. 

2. 가계부

배열에서 원소 값을 변경하는 쿼리와 구간 합을 구하는 쿼리가 주어졌을 때, 이를 효율적으로 계산하는 자료 구조가 필요한 문제다. 이러한 자료구조로는 Fenwick Tree (혹은 Binary Indexed Tree) 라는 것이 잘 알려져 있다. 이에 대해서는 이 링크를 참고하면 좋다. Fenwick Tree가 아니더라도 Segment Tree로도 문제를 해결할 수 있다 (링크). 그 외 다양한 이진 트리 자료구조를 사용하면 O(QlgN)에 문제가 해결된다. 

몰랐다면 이번 기회에 알아가길 바라는 마음으로 문제를 넣었다. 꽤 기초적인 자료 구조이고 인터넷에도 리소스가 많으니 꼭 알아가자.

3. Horror List

처음 Horror Index가 0인 정점을 큐에 넣어가면서 Horror Index를 계산해 나가자. HI가 0인 정점에 인접한 정점들은 HI가 1이 될 것이고, 또 인접한 정점들은 HI가 2가 될 것이고, 이미 다른 정점에 의해서 HI가 방문되었으면 다시 방문할 필요가 없고 (어차피 그보다 더 큰 값일 것이기 때문).. 이런 식으로 BFS를 사용해서 선형 시간에 시뮬레이션 하듯이 해결할 수 있다.

사실 Horror Index는 해당 정점과 가장 가까운 호러 무비 정점과의 거리라는 것을 쉽게 알 수 있다. 몰라도 상관없지만...

4. Juice

다양한 풀이가 있는데, 여기서는 가장 쉬운 Tree DP 풀이를 소개한다. DP[x][c] = (x번 정점의 부모에서 c 이상의 전기가 나올 때, 서브트리에서 최대 몇 개의 가구를 밝힐 수 있는지) 라 정의하자. DFS를 하면서 DP 테이블을 채울 것인데, 자식의 DP 테이블을 통해서 현재 정점의 DP 테이블을 구성해야 한다. 

일단은 현재 정점에 불을 밝히는 것도 생각하지 말고 용량 제한도 생각하지 말자. 자식이 여러개 (v1, v2 ... vk) 라고 생각하면, DP[x][c] = Max(C1 + C2 ... + Ck = c) DP[v1][C1] + DP[v2][C2] + DP[v3][C3] + ... 과 같은 형태가 될 것이다. 자식이 2개 정도면 O(100^2) 에 현재 정점 처리가 되겠지만 그렇지 않으니 경우는 지수적으로 불어 버리고 답이 없어진다. 그런데, 저러한 값의 최대를 DP로 구하면 어떨까?

DP 값의 상태 전이를 구하기 위해서 DP를 사용한다는 게 미친 거 같아 보이지만, 해 보면 아주 깔끔한 풀이가 나온다. DP2[i][x] = (i번 자식까지 고려했고 x만큼의 용량을 나눠줬을 때 최대로 밝혀진 집의 수) 라고 정의하자. O(자식의 수 * C^2)에 DP 테이블을 채우면 현재 정점의 DP 값을 알 수 있다. 모든 자식의 수 합은 O(N)이므로 이렇게 하면 O(NC^2)에 문제를 해결할 수 있다. 용량 제한은 DP[v1][C1]을 가져오는 대신 DP[v1][min(용량, C1)] 을 가져오는 식으로 추가할 수 있고, 현재 정점을 밝히는 것도 처리 가능하다. 

DP를 합치기 위해서 DP를 사용하는 이 아이디어는, 자식이 2개 이상인 일반적인 트리를 이진 트리로 변환해서 문제를 해결하는 방식이라고도 생각할 수 있다. K개의 자식이 존재한다면, 이를 자식 하나와 K-1개의 자식 덩어리로 나누고, 또 다른 자식 하나와 K-2개의 자식 덩어리로 나누는 식으로 앞선 DP 과정을 생각해 볼 수 있다. 이진 트리에서는 자식 두개를 O(C^2)에 합칠 수 있으니 이런 식으로 자식을 나눠주면 다항 시간 안에 문제가 해결되는 것이다.

5. Money for Nothing

일단 가격과 날짜를 x좌표와 y좌표로 매칭시키면 좌표 평면 상의 점으로 볼 수가 있다. 어떠한 문제들은 좌표 평면 상에 모델링을 하면 직관적인 아이디어나 기하적인 성질이 눈에 팍 들어오는 경우가 많은데, 이 문제도 모델링을 하면 굉장히 깔끔하게 변형된다. 구매 후보를 빨간 점, 판매 후보를 파란 점이라고 하면, 다음과 같은 문제가 된다. 

 * xy축에 평행하며, 빨간 점을 왼쪽 아래, 파란 점을 오른쪽 위 모서리로 하는 직사각형 중 최대 넓이를 구하여라.

먼저, 난잡하게 나열되어 있는 빨간 점과 파란 점을 정렬된 순서로 깔끔하게 만들 수 있다. 어떠한 빨간 점 i의 왼쪽 아래에 다른 빨간 점 j가 존재한다면, 이 빨간 점은 필요없는 점이다. i를 고르는 것보다 j를 고르는 것이 무조건 이득을 주기 때문이다. 비슷한 논리로 어떠한 파란 점 i의 오른쪽 위에 다른 파란 점 j가 존재한다면 이 파란 점도 필요 없다. 고로, 처음에 필요없는 빨간 점과 파란 점을 모두 제거해 준다. 이는 점들을 정렬하고, 현재 점보다 왼쪽에 있으면서 y좌표가 최소인 점을 관리하는 식으로 O(nlgn)에 쉽게 구할 수 있다. 이렇게 되면, 빨간 점과 파란 점은 모두 오른쪽 아래를 향하는 체인의 형태가 된다. 

이제, 흔히 Divide and Conquer Optimization 이라고 불리는 분할 정복 기법을 사용해 보자. D&C Optimization을 사용하기 전에 다음 사실을 알아야 한다. 

 * 각 점에 x축 순으로 인덱스를 붙이자. 빨간 점 i에 대해서 최적해를 내는 파란 점 j를 Opt(i) 라고 하자. (같은 것이 여러 개 있을 경우 최소의 인덱스로!) Opt(i) <= Opt(i+1) 을 만족한다.

기하적인 방법이나 수식 전개를 통해서 저 사실은 어렵지 않게 증명할 수 있다. 문제점이 되는 것이라면 어떤 i에 대해서 매칭 가능한 파란 점이 존재하지 않을 수 있다는 것인데, 이는 음수 코스트를 허용해 주는 식으로 가능하다. 즉, X Y 둘 다 큰 파란 점만 매칭시키는 것이 아니라, X Y 둘 다 음수가 아니기만 하면 매칭시켜주는 것이다. 이렇게 하면 어차피 음수라서 답에 영향을 주지 않고, 매칭이 전혀 존재하지 않는 이상 모든 i에 대해서 최적해를 내는 파란 점이 존재한다.

이제 다음과 같은 분할 정복을 생각하자. Solve([빨간 점 구간], [파란 점 구간]) 은, 빨간 점 구간에 있는 점들과 파란 점 구간에 있는 점들 중 최적 매칭 쌍을 찾겠다는 뜻이다. 빨간 점 구간의 중점을 잡고, 파란 점 구간 전체를 선형 시간에 탐색해서 Opt(i)를 찾아보자. 그렇다면 그보다 왼쪽에 있던 빨간 점은 Opt(i) 이하의 인덱스랑만 매칭이 되고, 오른쪽에 있던 빨간 점은 Opt(i) 이상의 인덱스랑만 매칭이 된다. 이렇게 하면 재귀적으로 두개의 부분문제로 문제가 분할된다. 시간 복잡도 분석은 자명하지 않지만, 빨간 점 구간은 결국 O(lgN) 개의 이진 트리처럼 나뉘어 질 것이고, 이진 트리의 각 "층" 의 파란 점 구간 길이 합이 M임을 관찰하면 결국 O(MlgN) 정도에 작동함을 알 수 있다. 

잘 이해가 안 가면 링크1 링크2 이 도움이 될 수도 있다. 링크1 에는 비슷한 유형의 연습 문제도 많이 있으니 풀어보면 좋을 것이다. BOJ 11001 김치 문제는 이 분할 정복 기법을 통해서 풀 수 있는 가장 쉬운 문제에 속하니 연습 삼아 풀어보기 좋다고 생각한다.