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

1. 작은 새

각각의 쿼리가 그다지 연관성이 없어보이니, 그냥 K가 고정됐다 치고 각 문제를 독립적으로 풀어보자. 결국 쿼리당 O(n)에 해결하면 되니 말이다. 

O(n^2) 동적 계획법은 다음과 같이 어렵지 않게 할 수 있다. dp(i) = 1번에서 i로 오는 데 필요한 최소의 힘든 점프 수라 하면, 그 전 위치를 j라 했을 때에 대한 식으로 동적 계획법 표를 채울 수 있다. 기본적으로 dp(j)를 가져올 수 있지만, 만약 H_j <= H_i 면 dp(j) + 1을 가져와야 하는 식일 것이다.

H_j <= H_i 일때 dp(j) + 1이 아니라 dp(j)를 가져올 수 있으면 참 좋을 것이다. dp(i) = Min(dp(i-1), dp(i-2), dp(i-3) .... dp(i-K)) 의 형태가 나올 것인데, 데큐를 사용해서 sliding window minimum을 구하는 식으로 dp table을 O(n)에 채울 수 있기 때문이다. (데큐를 사용한 구간 최솟값 알고리즘을 모른다면 링크1 링크2 링크3 에서 이해하고 가자.)

물론 그 희망이 현실이 될 수 없지만, 그래도 유용한 관찰을 여기서 이끌어 낼 수 있다. Sliding window로 C = Min(dp(i-1), dp(i-2), dp(i-3) .... dp(i-K)) 를 구할 수 있다면, dp(i) = C 이거나 dp(i) = C+1 이라는 것을 알 수 있다. 후자는 dp(j) = C인 원소들이 전부 H_j <= H_i일 경우에 일어날 것이고, 그렇지 않다면 항상 C가 가능하다. 우리는 C가 무엇인지 아니까, 답이 C인지 C+1인지만을 생각할 수 있으면 된다. 다시 말해, dp(j) = C이면서 H_j > H_i인 원소가 있는지 없는지를 알 수 있으면 된다. 

그렇다면, Sliding window가 단순히 dp(j)만을 비교하는 게 아니라, dp(j)가 같을 때 H_j가 큰 것을 우선적으로 처리할 수 있게 하면 되지 않을까? 다시 말해, dp값이 증가하는 순서대로 값들을 관리하고, 만약에 값이 같다면 H_i가 작은 순서대로 값을 관리할 수 있게 하면 어떨까? 이렇게 하면, 해당 비교 기준에서의 "최솟값"을 확인했을 때, 답이 C인지 C+1인지 한번에 알 수 있게 된다. 최솟값은 dp(j)를 최소화하는 한에서 H_i를 최대화했기 때문이다. 고로 그 원소의 높이가 H_i보다 크다면 답은 C, 그렇지 않다면 답은 C+1이다. 고로 총 O(N)에 dp 배열을 채울 수 있다. 시간 복잡도는 O(NQ)이다.

2. 문자열 생성

앞의 문자와 뒤의 문자가 같은 경우에는 선택지가 없다. 그 중 작은 것을 무조건 골라야 한다. 

앞의 문자와 뒤의 문자가 같은 경우가 문제이다. 남은 S를 뒤집은 문자열을 Sr이라 하고, 둘의 공통 접두사의 길이를 P라 하자. 

* Case 1. P 이하만큼 앞에서 빼다가 뒤에서 빼기 시작 (혹은, 뒤에서 빼다가 앞에서 빼기 시작) : 그게 최적이면, 앞에서 빼든 뒤에서 빼든 상관없다. 뒤에서 빼기 시작했으면 P만큼 뺐을 때 앞에서 빼면 되고, 반대로 앞에서 빼기 시작했으면 P만큼 뺐을 때 뒤에서 빼면 되기 때문이다. 

* Case 2. P 초과만큼 앞/뒤에서 연속적으로 빼는 경우 : 앞에서 빼는 것과 뒤에서 빼는 것이 명백히 차이가 난다. S가 사전순으로 Sr보다 앞서면 앞에서, 아니면 뒤에서 빼주자. 

고로 S가 사전순으로 Sr보다 앞섰을 때 앞, 아니면 뒤를 뽑아주면 된다. 한 문자 뺄 때 O(n) 시간이 소모되니 총 O(n^2) 에 문제가 해결된다. Suffix array를 사용하면 사전순 비교를 효율적으로 할 수 있고, 이를 통한 O(n) 풀이도 있다. (통상적으로 O(nlgn)에 풀지만)

3. 수상 택시

결국 상근이는 0에서 m으로 가야 한다. 그렇다면, 그 사이에서 어떻게 길을 꼬여서 갔던 간에 0을 처음 방문한 시간 < 1을 처음 방문한 시간 < 2를 처음 방문한 시간 < ... < m을 처음 방문한 시간의 관계가 있다. 고로, 만약에 시작점 < 도착점이면 시작점에 처음 방문했을 때 태우고 도착점에 처음 방문했을 때 내려주면 무조건 태울 수 있다. 즉 어떤 경우에도 처리 가능하니 그냥 이런 건 없다 치자. 

승객 i 경로는 항상 시작점 > 도착점을 만족한다고 하자. 이를 Si, Ei라 한다. Si > Ei라는 것은, 어떠한 시간에 Si에 있다가, 그 후에 Ei에 있고,  그 다음에 Si에 다시 돌아와야 한다는 것을 뜻한다. 그렇다면, 최소 Ei -> Si로 한번은 거꾸로 가는 것이 필요하다는 것을 뜻한다. (거꾸로 간다는 것은 돌아온다는 것을 함의한다.) 이들을 [Ei, Si] 형태의 구간이라고 생각하고, 구간 합집합의 길이 (즉, 단 한개의 구간에라도 포함된 [i-1, i]의 개수) 를 C라고 하자. 

답의 하한은 2C+ M 이다. 적어도 저 길들은 다 i -> i-1의 형태로 한번은 거쳐가야 하고 거기에 돌아오기까지 해야 하기 때문이다. 이제 그것이 답임을 증명해보자. 구간의 합집합을 하면 몇개의 구간은 덩어리로 붙어있고, 몇개는 그렇지 않다. 덩어리로 붙어있는 것을 하나의 구간으로 생각해주고, 0 > 1번 구간 덩어리 끝점 > 1번 구간 덩어리 시작점 > 1번 구간 덩어리 끝점 > 2번 구간 덩어리 끝점 > 2번 구간 덩어리 시작점 > 2번 구간 덩어리 끝점 > M 과 같이 이어주자. 2C + M의 비용으로 모든 경우가 처리됨을 알 수 있다. 

구간의 합집합 길이는 sweep line으로 알 수 있다. Ei 시점에 구간 하나 추가, Si 시점에 구간 하나 제거와 같은 이벤트를 2N개 만들어 주고 정렬하자. 이벤트를 순차적으로 처리하면서, 만약에 추가된 구간 개수가 0 초과면 대응되는 길이를 C에 더해주자. 시간 복잡도는 O(nlgn) 이다. 

설명이 잘 이해가 가지 않는다면 다른 분의 풀이를 보는 것도 좋다. 내용은 같다. 

http://blog.naver.com/jh05013/221066385729

4. 데크 소트

데크를 마지막에 이어붙여야 하기 때문에, 결국 최종적으로 각 데크는 가장 작은 수들 몇개, 그 다음 작은 수들 몇개.. 가장 큰 수들 몇개를 순서대로 포함하는 형태여아 한다. 그리고 데크 개수는 최소화해야 한다.

일단 헷갈리니 모든 수들이 다르다고 생각해보자. 그리디 알고리즘을 사용할 것인데, 최대한 많은 수를 첫번째 데큐, 그 다음 많은 수를 두번째 데큐... 에 넣는 식으로 각 데큐에 넣을 수 있는 한 많이 넣어서 개수를 최소화할 것이다. 데큐에 들어간 수들을 크기 순으로 정렬하면, 그 수들이 추가된 인덱스가 감소하다가 증가할 것이다. 고로 알고리즘은, 크기순으로 인덱스가 감소하다가 증가하는 형태를 유지할 때까지 최대한 많은 숫자들을 넣은 방식이 될 것이다. 수들을 크기순으로 정렬하면 크게 어렵지 않다. 

숫자들이 같을 수 있으면 알고리즘이 크게 다를까? 이 때는 같은 수를 고르더라도 가능한 인덱스의 경우의 수가 많을 것이다. 하지만 전략은 똑같다. 만약에 감소 모드라면, 현재 넣을 수 있는 수 중 (즉, 크기가 가장 작은 수 중 하나이며 인덱스가 맨 마지막보다 작음) 인덱스가 최대인 것을 넣고, 그게 안되면 증가 모드로 바꾼 후 똑같은 것을 하면 된다. O(nlgn)에 문제를 해결할 수 있다. 물론 O(n^2)도 통과한다.