BOJ 17258 - 인기가 넘쳐흘러

BOJ 17258 - 인기가 넘쳐흘러

$O(NK^2)$ Solution

$dp[i][j][k]=$시간 $i$를 보고 있고, 부를 수 있는 친구 수가 $j$ 명이고 $k$ 명이 이미 파티장에 들어와있을 때로 두고, $O(NK^2)$에 문제를 해결할 수 있다.

int dp[302][301][301];  
void solve() {  
   memset(dp, -1, sizeof dp);  
   int N, M, K, T;  
   cin >> N >> M >> K >> T;  
   vi people(N + 5);  
   for (int i = 0; i < M; i++) {  
      int a, b;  
      cin >> a >> b;  
      people[a]++;  
      people[b]--;  
   }  
   for (int i = 1; i <= N; i++) people[i] += people[i - 1];  
   int ans = 0;  
   dp[1][K][0] = 0;  
   // i 시간을 보고 있고  
   for (int i = 1; i <= N; i++) {  
      // 남은 들어오게 할 수 있는 친구 수가 j이고  
      for (int j = K; j >= 0; j--) {  
         // 이미 들어와있는 친구 수가 k일 때  
         for (int k = 0; k <= K; k++) {  
            if (dp[i][j][k] == -1) continue;  
            if (people[i] >= T) {  
               dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k] + 1);  
               ans = max(ans, dp[i + 1][j][0]);  
            } else {  
               dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);  
               ans = max(ans, dp[i + 1][j][k]);  
               int need = max(0, T - people[i] - k);  
               if (j >= need) { // 더 들어오게 할 친구가 충분할 때  
                  dp[i + 1][j - need][k + need] =  
                     max(dp[i + 1][j - need][k + need], dp[i][j][k] + 1);  
                  ans = max(ans, dp[i + 1][j - need][k + need]);  
                  dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);  
               }  
            }  
         }  
      }  
   }  
   cout << ans;  
}

$O(NK)$ Solution

일반성을 잃지않고 어떤 구간에서 $M$명 이 모여서 $T$ 이상이 되는 구간이 없다고 하자.

그렇지 않다면 $T$ 이상인 구간의 길이만큼 정답에 더해주고 나머지 구간들을 분리해줄 수 있다.

$dp[i]$ 를 부를 수 있는 남은 친구가 $i$ 명 남았을 때 구간에서의 최대 정답이라고 하자.

그리디하게 가장 구간의 첫 시간에 $i$ 명을 다 투입시키는 것이 최적이다.

이건 $O(NK)$ 에 모두 구해줄 수 있다.

그런데 투입시킬 명수는 모든 구간에서 $O(N)$로 제한된다. 서로 다른 친구 수가 $O(N)$ 개이기 때문이다.

이제 $dp2[i][j]$ 를 $i$ 번째 구간에서 쓸 수 있는 친구 $j$명이 남았을 때의 최적이라고 한다면 모두 순회해보며 DP를 돌리면 $O(NK)$ 이다.