RUN@KAIST 7/6 방학 연습 풀이

1. 워크스테이션 배정

그리디 알고리즘으로 해결할 수 있다. 모든 배정을 시작점 순으로 정렬하자. i번 배정을 할 때, 만약에 이미 끝난 다른 배정 중, 끝난 시간과 현재 시간과의 M 이하인 것이 있다면 그 배정과 같은 워크스테이션을 쓴다고 생각하자. 만약에 그러한 배정이 여럿 있다면 차이를 최대화 하는 것이 이득이다. (차이를 괜히 작게 줘 봤자 시작점이 큰 다른 배정에게 도움이 안 되니까) 이러한 그리디 알고리즘을 priority queue 등으로 구현하면 O(nlgn)에 문제를 해결할 수 있다.

2. Identifying Map Tiles

주어진 문자열을 비트마스크로 읽어서 출력하면 되는 단순 구현 문제이다. 

(사실 1번 2번은 일단 placeholder로 넣은 거였습니다. 즉 나중에 다른 문제로 고칠 계획었습니다. 하지만 제가 그 날 도저히 시간이 없어서 차마 고치지를 못했습니다. 앞 두 문제가 너무 쉬운 건 그래서입니다. 죄송합니다 ㅠㅠ)

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

철판의 높이와 너비를 고정시켰을 때 (즉, 높이와 너비를 바꿀 수 없다 칠 때) 모든 철판의 너비가 줄어들어야 한다는 조건이 정말로 중요할까? 너비가 같은 철판이 없다면, 단순히 정렬을 하면 모든 철판의 너비가 줄어들 게 바꿀 수 있다. 고로 줄어들어야 한다는 조건은, 너비가 모두 다르기만 하면 아무 상관 없다는 사실을 알 수 있다. 이렇게 됐을 때, 우리는 일부 철판의 높이와 너비를 교환해서, 모든 너비를 서로 다르게 하고 높이의 합을 최대화해야 하는 문제가 된다. 사실 너비의 합을 최소화한다고 생각하는 것이 더 편할 것 같다.

여기서 독특한 접근을 시도해 보자. 수직선 상의 모든 정수를 정점으로 보고, N개의 쌍에 대해서 너비 정수와 높이 정수를 잇는 에지를 이어주자. 물론, 실제로 모든 수직선 상의 정수가 정점으로 필요한 것은 아니고, 너비 / 높이로 등장하는 2N개 정도의 정점만이 필요할 것이다. 그래프로 문제를 바꿨을 때, 우리는

 * 각 에지의 양 끝 점 중 하나를 색칠해야 하고

 * 각 에지에 대해서 색칠한 정점이 겹치면 안 된다

 * 색칠한 정점의 가중치 합은 최소화해야 한다.

라는 조건으로 문제를 바꿀 수 있다. 이제 이 문제를 풀어보자.

항상 답이 존재하니, 모든 컴포넌트에 대해서 간선의 개수는 정점의 개수를 넘지 않음을 알 수 있다. 고로, 간선의 개수가 정점의 개수 이하인데, 연결 그래프니까 케이스는 단 두가지이다. 두 케이스에 대해서 살펴보자.

 * 1. |간선 개수| = |정점 개수| - 1 -> 트리 그래프이다. 단 하나의 정점을 색칠하지 않게 될 것이다. 우리는 색칠한 정점의 가중치 합을 최소화하고 싶으니 아무래도 그 정점의 값이 크면 좋을 것이다. 그럼 최댓값을 가지는 정점 빼고 모든 정점을 색칠할 수 있을까? 해당 정점을 루트로 한 rooted tree를 고려해 봤을 때, parent(i) 와 i를 잇는 간선들이 i를 색칠했다고 치면, 루트를 제외한 모든 정점이 색칠된다. 원하는 색칠 방법이 존재하니 가중치 합은 전체 - (최대 가중치 노드) 이다.

 * 2. |간선 개수| = |정점 개수| -> 문제에서 답이 항상 존재한다고 했으니, 결국 어떻게든 색칠은 할 수 있다. 근데 어떻게 색칠하던 간에 모든 정점이 색칠된다. 고로 모든 정점의 수 합을 더한다. (사실 색칠 방법은 해당 그래프가 유일한 사이클을 가진다는 점을 알면 1번의 아이디어로 구할 수 있다. 물론 이 문제에서는 필요 없다.)

고로, 위 방법으로 만든 그래프의 컴포넌트 정점 개수와 간선 개수만 알 수 있으면 아주 쉽게 문제를 풀 수 있다. 

4. 생산성 향상

어떠한 노동자 i에 대해서, 해당 노동자보다 늦게 일을 시작하고 일찍 일을 끝내는 다른 노동자 j가 존재한다면, 해당 노동자를 착한 노동자, 그렇지 않다면 그 노동자를 나쁜 노동자라고 하자. 만약에 모든 노동자가 나쁜 노동자라면, 구간을 시작점 순으로 정렬하면, dp[i][j] = (1 ~ i까지의 노동자를 j개의 그룹으로 묶었다) 는 식의 동적 계획법을 사용해서 문제를 해결할 수 있다. 

착한 노동자를 넣는다면, 이제 그룹의 형태는 (나쁜 노동자 + 착한 노동자 0명 이상) / (나쁜 노동자 + 착한 노동자 0명 이상) / (...) / (착한 노동자들) / (착한 노동자들) 과 같은 형태로 이루어진다. 여기서 몇가지 관찰을 하자면,

 * 나쁜 노동자들과 같이 일하는 착한 노동자들은, 나쁜 노동자들 그룹의 생산성을 전혀 해치지 않을 수 있다. 착한 노동자들에 대해서, 그에 대응하는 나쁜 노동자들이 있다. 그 나쁜 노동자의 그룹에 들어간다면, 나쁜 노동자의 근무 시간이 자신의 부분집합이니, 해당 그룹의 생산성에 변화가 없다.

 * 나쁜 노동자들과 같이 일하지 않는 착한 노동자들은, 혼자 일한다. 두 명 이상이 일할 경우에는 혼자 일하는 것보다 생산성이 떨어진다. 이들은 그냥 나쁜 노동자들과 같이 일하게 두는 게 낫다.

혼자 노는 착한 노동자가 K명이라고 하자. 어차피 나머지 착한 노동자들은 나쁜 노동자들한테 보낼 테니까, 혼자 노는 노동자들은 생산성이 큰 걸 그리디하게 뽑는 게 최적이다. 나머지 p - K개의 그룹은, 나쁜 노동자들에 대해서 DP를 돌린 값을 사용해서 최적의 배정을 찾을 수 있다. 시간 복잡도는 DP를 돌리는 데 걸리는 O(N^3)이다.