RUN@KAIST 2018 겨울 2주차 연습 문제

1. 제로

스택을 구현하면 되는 단순한 문제입니다.

2. 공항

비행기가 올 때 공항 게이트를 골라야 하는 데, 각 상황에서 고를 수 있는 공항 게이트 중 가장 큰 것을 골라야 한다는 그리디 접근을 생각해 볼 수 있습니다. 그 위치를 비워두면서 도착하는 비행기의 수를 늘릴 수 없기 때문입니다. ($i$번째 비행기가 비워둔 자리가 끝까지 비었다면 비우는 의미가 없으니 모순입니다. 그렇지 않다면, 비워둔 자리를 다른 비행기 ($j$번째, $j > i$)가 채울 것인데, 그렇게 하느니 $i$번째 비행기와 위치를 바꾸는 것이 이득입니다. 이런 식으로 계속 진행하면 그리디 알고리즘이 최적임을 증명할 수 있습니다.) 이 알고리즘을 그대로 구현하면 $O(PG)$ 시간이 걸려 시간 초과가 납니다.

이를 해결하는 방법은, std::set 자료구조를 사용하는 것입니다. std::set에 가능한 모든 게이트 위치를 저장해 놓고, 각 비행기가 들어올 때마다, $g_i$보다 작거나 같은 수 중 가장 큰 수를 지워주면 됩니다. 이는 upper_bound 함수로 $g_i$보다 큰 수 중 가장 작은 수를 찾으면 알 수 있습니다. $O(G + PlgG)$ 시간에 문제를 해결할 수 있습니다. 그 외 Union-Find나 세그먼트 트리를 사용해서도 문제를 해결할 수도 있습니다. (Union-Find는 $O(G + P\alpha(G))$ 로 시간이 약간 더 빠릅니다.)

3. 허니버터칩

$M=0$ 일 경우 간단한 동적 계획법을 사용해서 문제를 해결할 수 있습니다. $DP[0][i] =$ ($i$번 물건을 고를 차례고, 그 전에 다른 물건을 고르지 않았을 때), $DP[1][i] =$ ($i$번 물건을 고를 차례고, 그 전에 다른 물건을 골랐을 때) 로 점화식을 정의하고, $DP[*][i+1]$ 과의 관계를 찾으면 선형 시간에 쉽게 문제가 해결됩니다.

문제는 $M$개의 추가 봉지가 아무 위치에 아무 순서로 들어갈 수 있으며, $M = 100$으로 추가 봉지의 개수도 상당히 많다는 것입니다. 일단은, $M \leq 10$ 정도라고 생각한 후 지수 시간 풀이를 생각해 봅시다. 이 때는 집합에 대해서 DP를 하면 (Bit DP) 생각보다 어렵지 않게 문제를 해결할 수 있습니다. $DP[0][S][i] =$ ($i$번 물건, 혹은 추가 봉지 집합 $S$에서 고를 차례고, 그 전에 다른 물건을 고르지 않았을 때) 로 점화식을 정의한 후, $i$번 물건 대신 추가 봉지에서 고르는 경우에 대해서 더 고려해 주면 비슷한 동적 계획법을 $O(N2^M)$에 해결할 수 있습니다. 물론 문제를 해결하기에는 턱없이 부족합니다.

위 DP의 시간 복잡도를 줄이기 위해서는 한가지 관찰이 필요합니다. 추가 봉지 집합에서 과자를 고를 때, 어떠한 경우에는 과자를 버리기 위해서 리스트에 끼워넣기도 하고, 어떠한 경우에는 과자를 가져가기 위해서 리스트에 끼워넣기도 합니다. 그런데, 과자를 버리고자 한다면 가장 적은 조각이 들어간 과자를 버리지 않을 이유가 없습니다. 반대로, 과자를 가져가고자 한다면 가장 많은 조각이 들어간 봉지를 집지 않을 이유도 없습니다!

관찰을 따라서 문제를 다시 살펴봅시다. 먼저, 추가 봉지들을 조각의 개수 순으로 정렬합시다. 결국 버리는 과자들은 조각이 적은 과자들일것이고, 가져가는 과자들은 조각이 많을 것이기 때문에, 현재 가져갈 수 있는 과자들은 정렬된 배열에서 연속 구간을 이룹니다. $DP[0][l][r][i]$ = ($i$번 물건, 혹은 추가 봉지 집합 $[l,r]$에서 고를 차례고, 그 전에 다른 물건을 고르지 않았을 때) 로 정의하면 똑같은 DP를 시간 복잡도 $O(NM^2)$에 해결할 수 있습니다.

4. 최고인 대장장이 토르비욘

철판을 90도 돌릴 것인지 말 것인지를 전부 결정했다고 생각해 봅시다. 일단은, 너비가 감소해야 한다는 조건은 함정입니다. 너비가 감소되게 정렬한 후, 그 순으로 붙이면 그만이기 때문입니다. 고로, 너비가 감소해야 한다는 조건은 실제로 "너비가 같은 두 철판이 존재하면 안된다" 라는 조건으로 다시 해석해야 합니다. 또한, 높이 합은 전체 합 - (너비 합) 이니, 너비 합을 최소화해야 한다는 조건으로 해석합시다.

이렇게 되면, 문제는 다음과 같이 사뭇 다르게 해석됩니다.

" N개의 두 정수 쌍이 주어질 때, 두 정수 중 하나의 정수를 골라서, 전체 정수 중 똑같은 것이 없게 하고, 또한 정수들의 합을 최소화하라. "

해석에서 "정수를 골랐다"는 것은, 그 정수를 너비로 한다는 뜻입니다.

여기서 재미있는 발상을 할 수 있습니다. 각 숫자를 정점으로 하고, 정수 쌍을 간선으로 한 그래프를 생각해 봅시다. 이 문제는 결국 모든 간선에 서로 다른 정점을 매칭시켜, 정점에 적힌 수의 합을 최소화하는 문제로 바꿀 수 있습니다. 단순히 생각하면 $10^9$개의 정점이 필요하지만, 좌표 압축을 통해서 정점의 개수를 $O(N)$개로 줄일 수 있습니다. 

각각의 연결 컴포넌트를 생각해 봅시다. 올바른 답이 항상 존재한다고 했으니, (정점의 개수) ≤ (간선의 개수) 인 경우는 어차피 모든 정점을 쓸 수 밖에 없고, 고로 정점의 번호 합을 적어주면 됩니다. 그렇지 않을 경우, 연결 컴포넌트에서 (정점의 개수) > (간선의 개수) 를 만족하니 컴포넌트는 트리의 형태를 띄게 됩니다. 하나의 정점은 포기해야 하는데, 최댓값을 포기하는 게 값을 줄이는 데 최선일 것입니다. 그리고 이것이 가능함을 보일 수 있습니다.

임의의 정점을 루트로 한 rooted tree를 만들면, 리프부터 하나씩 매칭시켜 나갈 때 루트를 제외한 모든 정점을 매칭시킬 수 있습니다. 고로 최댓값을 포기하게 할 수 있으며, 최댓값을 제외한 정점의 번호 합을 적어주면 됩니다.