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

1. 레이저

원점을 지나는 직선이 해당 선분을 맞추려면 기울기가 어떠한 수의 구간 사이에 있어야 한다. 그러니 2차원 평면에 직선을 쏴서 선분을 맞춘다고 생각하지 말고, 수직선에 구간이 있는데 점을 몇 개 넣어서 구간들을 덮는다고 생각해보자. 모든 점들이 1사분면 위에 있고 x/y축에 닿지도 않기 때문에, 각 구간은 어떠한 분수와 분수 사이의 폐구간으로 쉽게 표현할 수 있다. 하지만, 더 간단하게 분수가 아닌 정수로 생각해 줄 수도 있다. 각 분수의 정확한 값이 아닌 대소 관계만이 중요하기 때문이다. 고로 좌표 압축을 통해 분수를 적당한 0 - 2n-1 사이의 정수로 바꿀 수 있다. 

이제, 0 ~ 2n-1 사이의 정수를 시작점 끝점으로 가지는 n개의 폐구간이 있을 때, k개의 실수를 골라서 최대의 구간을 덮는 것으로 문제를 변환했다. (한 구간을 두번 덮을 수 없다) 고르는 수가 실수라는 점에 주목해야 하는데, 예를 들어 [?,10] [11,?] 과 같은 두 구간이 있을 때 10.5라는 숫자를 고르는 것이 어떤 의미를 가지는 지 생각해 보자. 여하튼 고르는 수가 정수이면 편한 게 사실이기 때문에 좌표 범위를 "또" 늘려서 이를 해결한다. 이는 간단한데, 모든 구간의 수 크기를 두 배로 늘려주면 된다 (그러면 20을 고르는 건 10, 21을 고르는 건 10.5를 고르는 것과 같은 효과이다)

이제 k개의 실수도 정수로 바꿨으니, 본격적으로 풀이에 돌입하자. DP로 해결한다. 정의는 다음과 같다. 

* dp(i, j) : i개의 정수를 골랐고, 마지막에 고른 점 번호가 j 이하일 때 최대 몇 개의 구간이 덮이는가?

j번을 안 고르면 dp(i, j-1)인 것이 명확하다. j번을 골랐을 때는 다음에 골라야 하는 점 k를 조심히 골라야 한다. j와 k를 동시에 포함하는 (즉 두 번 덮인) 구간이 존재하면 안 되기 때문이다. 즉, Si <= k < j <= Ei 를 만족하는 구간 i가 있으면 안된다는 것이다. 

이를 더 정리하면, 끝점이 j 이상인 구간 중 시작점이 가장 작은 것을 Low(j) 라 하면, k < Low(j) 라는 조건으로 볼 수 있다. Low(j)를 전부 구했다면, 답은 dp(i-1, min(Low(j), j) -1) + (j를 지나는 구간 수) 이다. 같은 구간을 두 번 세는 일이 문제 정의상 없기 때문에 생각해 줄 게 별로 없다. 

결국 Low(j), 그리고 j를 지나는 구간 수 (Stab(j) 라 하자) 를 어떻게 빠르게 구했다면, 시간 복잡도 및 공간 복잡도 O(kn) 에 문제가 해결된다. 공간 복잡도는 문제가 될 수 있는데, dp(i-1, *) 만 갖고 dp(i, *) 를 유추할 수 있으니 메모리를 돌려쓰면 (흔히 토글링이라고 한다) 공간 복잡도는 선형으로 줄일 수 있다. Low[], Stab[]은 O(n^2)에 자명하게 구할 수 있지만, 이보다 더 빠른 방법이 필요하다. 이를 최적화 해보자. 

먼저 Stab[] 을 보자. 구간이 [S, E]일 경우, Stab[S]++, Stab[E+1]--을 해주자. 이는 각 구간마다 O(1)에 가능하다. 이후 배열을 쭉 돌면서 Stab[i] += Stab[i-1] 을 대입해 주면 [S, E] 구간에 정확히 1씩 더해진 모습을 볼 수 있다. 부분합 배열을 거꾸로 생각한 것이라고 할 수 있다. (그래서 흔히 변홧값 배열이라고 부르는 테크닉이다.) 고로 O(N) 전처리에 Stab[] 이 구해졌다.

이제 Low[] 를 보자. Low(j) : 끝점이 “정확히” j인 구간 중 시작점이 가장 작은 것이라고 저장하면 간단히 테이블을 채울 수 있다. 이를 “j 이상”으로 바꿔야 하는데, j를 감소시켜 나가면서 Low(j) = min(Low(j), Low(j+1)) 과 같이 전파시켜주면 가능하다. 이 역시 O(N) 전처리에 구할 수 있다. 

총 시간 복잡도는 O(kn)이다. 여담으로 이 문제는 O(nlgn)에 풀 수도 있으며, 그 풀이가 블로그에 있다. 링크

2. 고용

어떠한 노동자들의 부분집합을 정했을 때, 내가 얼마의 임금을 지불해야 하는 지 생각해 보자. 임금에 대한 제약 조건은 최저임금, 그리고 자격증 비율이다. 식으로 쓰면, 노동자에게 실제 지불한 임금을 Wi라 했을 때 kQi = Wi >= Si를 만족해야 한다. 우리가 내야 할 전체 지불 임금은 sum(Wi) = ksum(Qi)이다. Qi는 고정된 값이니 k는 가능한 숫자 중에서 가장 작게, 즉 k = max(Si / Qi) 로 잡아야 한다. 즉, 부분 집합을 고정 시켰을 때 지불해야 하는 최저 비용은 max(Si / Qi) * sum(Qi) 이다. 이것을 W보다 작게 하며 노동자 수를 최대화해야 한다. 

k = max(Si / Qi) 가 고정되었을 때 최대 얼마의 노동자를 결정할 수 있는지를 생각해 보자. Sj / Qj <= k인 모든 노동자들에 대해서 Qi가 작은 것들을 순서대로 최대한 골라서, 그 합이 W/k을 넘지 않을 때까지 반복하고, 몇 개를 골랐는 지 세주면 된다. 꼭 정확히 k = Si / Qi인 노동자를 골라야 하는 게 아니라는 것을 유념하자. 이렇게 하면 O(n^2) 정도에 문제가 해결된다. 

최적화하기 위해서는, 노동자들을 Si / Qi 증가 순으로 정렬하자. priority queue를 가지고 다니면서, Si/Qi가 작은 노동자에서 큰 노동자들을 순서대로 넣어준다. 아까 넣은 노동자가 i라면 k = Si/Qi이다. 그리고 이 k는 갈 수록 증가할 것이다. 고로 priority queue에서 합이 W/k를 넘을 때까지 Qi가 큰 것들을 계속 빼주면 현재 몇 명의 노동자들을 고를 수 있는 지 알 수 있다. 한번 빠진 노동자를 다시 큐에 넣을 이유가 없기 때문이다. 

3. 곰돌이

http://koosaga.com/23