BOJ 15773 - Touch The Sky

문제 요약

 

풍선 \(N\)개가 있다. 각 풍선은 고도 \(L_i\)이하에서 불 수 있고, 불고 나면 고도가 \(D_i\)만큼 상승한다. 풍선은 한 번에 하나만 달 수 있다. 이 때, 불 수 있는 풍선의 최대 개수를 구하여라.

 

풀이

이런 문제는 원소들에 순서를 부여하려고 시도해보는 것이 도움이 된다. 다만, \(L_i\)나 \(D_i\)를 기준으로 쓰려고 하면 어렵지 않게 반례를 찾을 수 있다.

\((L_a,D_a)\), \((L_b,D_b)\)가 있다고 할 때, 반드시 a를 먼저 사용하고 b를 사용해야 하는 상황은 아래와 같다.

\(D_b > L_a, D_a \leq L_b\) 즉, b를 먼저 사용하면 a를 사용하지 못하고 a를 먼저 사용하면 b를 사용할 수 있는 경우이다.

양변을 더하면 \(D_a + L_a < D_b + L_b\)임을 알 수 있다. 즉, \(D+L\) 순서대로 정렬한 후 앞부터 사용하는 것이 항상 이득이다.

 

순서가 생겼으니 DP를 시도해보자. \(DP[i][j]\) = \(i\)번째 풍선까지 봤을 때 \(j\)개를 사용한 경우의 최소 고도

로 정의하자.

\(DP[i][j]\)는 \(DP[i-1][j] \leq L_i\)를 만족하는 \(j\)에 대해 \(DP[i][j+1]=min(DP[i][j+1], DP[i][j]+D_i)\)이다.

이를 그대로 풀면 55점짜리 서브태스크를 해결할 수 있다.

이제 이를 최적화해야 하는데, 일단 항 개수가 \(O(N^2)\)개라 당장 최적화할 수 없다.

 

결국 우리가 알고 싶은 것은 \(DP[n][k]\)가 정의되는 최대 \(k\)이다. 따라서, 각 \(i\)에 대해 \(DP[i][k]\)가 되는 최대 \(k = A_i\)에 대한 DP값만 관리한다고 생각해보자. 이를 \(B_i\)라 하겠다. 또한, 각 경우에 대해 사용한 풍선 중 최대 \(D_i\)를 \(C_i\)라 하자.

그러면 \((A_i,B_i)\)는

1) \(B_{i-1} \leq Li\) 

이 경우 그냥 \(i\)번째 풍선을 추가해주면 된다. 따라서 \((A_i, B_i) = (A_{i-1}+1, B_{i-1}+D_i)\)

2) \(B_{i-1} - C_i \leq Li, Di \leq C_i\)

이 경우 개수를 유지하며 고도를 낮출 수 있다. 따라서 \((A_i, B_i) = (A_{i-1}, B_{i-1}+D_i-C_i)\)

3) 그 외

이 경우 추가할 수 있는 풍선이 없다. 따라서 \((A_i, B_i) = (A_{i-1}, B_{i-1})\)

 

이러한 과정은 pq로 구현해줄 수 있다.

 

그렇다면, DP의 가장 뒷 항만 관리해도 되는 이유는 무엇일까?

이런 전략은 흔히 반례가 있다. 대표적으로, LIS가 그렇다.

7 8 9 1 2 3 4 5 6 의 LIS가 1 2 3 4 5 6 인 것처럼, DP의 앞 값부터 갱신되며 뒤 값이 갱신될 확률이 있기 때문이다.

하지만 이 문제에서는 그렇지 않다.

만약 어떤 풍선에 대해 DP가 앞에서 갱신되고 뒤에서 갱신되지 않았다면, 더 많은 풍선을 포함하는 집합에서는 \(i\)번째 풍선을 고르지 않고, 더 작은 풍선을 포함하는 집합에서는 \(i\)번째 풍선을 골랐다는 뜻인데 이는 최적이 아니기 때문이다.

 

뭔가 풀이를 야매로 적은 것 같은데, 자세한 풀이는 구사과님이 쓰신 공식 에디토리얼을 참고하자.