백준 30621 - 어? 금지 (C++)

문제

• 문제 링크

  
   BOJ 30621 - 어? 금지 
  

• 문제 요약

$N$개의 시각에 대해 수열 $t_N, b_N, c_N$이 주어진다.
성우가 규칙을 지키는 선에서 대회장에 줄 수 있는 최종 혼란의 최댓값을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 100,000$

$1 ≤ t_i, b_i, c_i ≤ 10^9$

$t_{i-1} < t_i;$ $b_i ≤ t_i$

알고리즘 분류

• 다이나믹 프로그래밍 (dp)
• 이분 탐색 (binary_search)

풀이

어떤 시각 $t_i$에서, 선택할 수 있는 분기 방향을 생각해보자.
이는 다음과 같을 것이다.

'어?'를 외치지 않는다.

지금부터 '어?'를 처음 외친다.

두 번째 경우의 연장선인데, $(t_i - b_i)$부터 지금까지 '어?'를 외친 적이 없는 경우 '어?'를 외친다.

$3$가지의 상태를 따로 관리할 필요 없이, 최댓값만을 취하면 된다.
이에 따라 아래와 같이 점화식을 정의하자.

$dp[i] :$ $0$_$base$로 할 때, $[t_0, t_i]$에서의 답.

---

그럼 각 세가지 분기 방향에 대해 다음과 같이 전이식을 정리할 수 있다.

$dp[i]$ $=$ $dp[i - 1]$

$dp[i]$ $=$ $c_i$

$(t_i - b_i)$보다 작은 첫 인덱스를 $prev$_$idx$라 할 때, $dp[i]$ $=$ $dp[prev$_$idx] + c_i$

한편, $prev$_$idx$를 찾을 때 현재 $i$에서 하나씩 내려가보며 찾는 것을 생각할 수 있다.

이 경우 $prev$_$idx$를 찾는 데에 $O(N)$의 시간이 걸릴 테고, $N ≤ 100,000$으로 시간 초과를 피할 수 없다.

문제의 입력 제한에서, $t_{i-1} < t_i$임을 확인하자.

$t_i$가 단조 증가 하므로 이분 탐색을 이용해 $prev$_$idx$를 $O(logN)$에 찾을 수 있다.

따라서, 문제를 $O(NlogN)$의 시간 복잡도로 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
 
    vector <int> t(n), b(n);
    for (int& i : t) cin >> i;
    for (int& i : b) cin >> i;
 
    vector <ll> dp(n); cin >> dp[0];
    for (int i(1); i < n; i++)
    {
        ll c; cin >> c;
        int prev_idx(lower_bound(t.begin(), t.begin() + i + 1, t[i] - b[i]) - t.begin());
 
        dp[i] = max(dp[i - 1], c);
        if (!!~--prev_idx) dp[i] = max(dp[i], dp[prev_idx] + c);
    }
 
    cout << dp[n - 1];
}

comment

끝