📝 문제 정보#
흐로닝언 박물관 방문 문제#
흐로닝언 박물관에서는 매일이 다릅니다. 어떤 날은 좋고 평화롭고 조용해서, 하루 종일 아름다운 그림, 조각, 그리고 다른 예술 작품들을 감상할 수 있습니다. 다른 날들은 더 바쁜데, 주말이나 공휴일에는 서두르는 방문객들, 높아진 입장료, 그리고 소리지르는 아이들로 박물관이 가득 찹니다. 이러한 불편함은 매우 다양합니다: 어떤 바쁜 날은 추가 학생 할인(studentenkorting) 덕분에 더 나을 수 있고, 어떤 조용한 날은 지진 위험 때문에 더 나빠질 수 있습니다.
박물관은 또한 정기적으로 기간 한정 특별 전시회를 개최하는데, 예를 들어 지역 축구 클럽 FC 흐로닝언, 마르티니토렌(Martinitoren), 또는 아이어발(eierbal, 지역 별미)에 관한 전시회 등이 있습니다. 이러한 전시회들은 매우 불규칙적일 수 있습니다: 어떤 것은 몇 주 동안 지속되고, 어떤 것은 단 하루만 지속되며, 같은 날에 여러 전시회가 있을 수도 있습니다.
자랑스러운 흐룬네허(Grunneger)로서, 당신은 각 전시회를 최소한 한 번씩은 방문하고 싶습니다. 다행히도, 당신은 뉴스레터를 구독하고 있어서 가까운 미래의 모든 전시회의 시작일과 종료일을 미리 알고 있습니다. 또한, 당신은 박물관의 단골 방문객이기 때문에 모든 혼잡도와 지진 패턴을 관찰해 왔으며, 특정 날짜에 박물관을 방문할 때 받게 될 불편함을 정확히 알고 있습니다.
가까운 미래에 계획된 모든 전시회를 보면서 총 불편함을 최소화하려면 어느 날에 박물관을 방문해야 할까요?
예를 들어, 첫 번째 샘플 케이스를 생각해보세요. 총 불편함을 최소화하려면, 첫 두 전시회는 둘째 날에 방문하고 마지막 전시회는 넷째 날이나 다섯째 날에 방문해야 합니다.
입력#
입력은 다음과 같이 구성됩니다:
- 첫 번째 줄에 두 정수 $n$과 $m$ $(1≤n,m≤2⋅10^5)$이 주어집니다. $n$은 가까운 미래의 일수이고, $m$은 그 기간 동안 계획된 전시회의 개수입니다.
- 두 번째 줄에 $n$개의 정수 $c$ $(1≤c≤10^9)$가 주어집니다. 각 날짜에 박물관을 방문할 때 받게 될 불편함을 나타냅니다.
- $m$개의 줄, 각각 두 정수 $s$와 $e$ $(1≤s≤e≤n)$가 주어집니다. 전시회의 시작일과 종료일을 나타냅니다. 시작일과 종료일은 포함됩니다: 전시회는 $s$일, $e$일, 그리고 그 사이의 모든 날에 방문할 수 있습니다.
출력#
흐로닝언 박물관의 모든 전시회를 방문할 때 받게 될 최소 총 불편함을 출력합니다.
🧐 관찰 및 접근#
- 예제 1번을 보자
- 3일에 3개를 다 방문할 수 있지만, 불편합의 합은 3
- 2일에 1,2번 전시, 4일이나 5일에 3번 전시를 보면 불편함의 합은 2
- 하루에 여러개를 보는게 좋을지, 아니면 더 불편함이 적은 날에 잘 보는게 좋을지…
- 날짜에 대한 DP를 하는게 좋지 않을까?
- DP를 하자!
- 그런데, 전시가 걸린다. 전시도 DP식에 포함되어어야 할텐데…
- 전시가 끝나는 날 순서대로 정렬하면, 앞에서부터 긁으면서 보는게 자연스러워질 것 같다.
- 그런데, 전시가 걸린다. 전시도 DP식에 포함되어어야 할텐데…
- 그렇다면 이런 식을 세울 수 있지 않을까?
- $\text{DP}[i]$ = 정렬된 전시들에서 $i$ 번째까지 전시들을 다 보는 최소 비용
- 전이 식은 이렇게 될까?
- $DP[i] = \min\limits_{0 < j \leq i}(DP[j-1] + C(j, i))$
- $C(j, i)$ 는 $j$ ~ $i$ 전시를 하루만에 볼 수 있다면 그 값중 최솟값, 아니라면 $\inf$
- $C(j, i) = min(c_{\max(s_j, s_{j+1}, \dots, s_i)}, \dots, c_{e_j})$
- $C$가 계산하기 힘들어서 제곱에서 줄이기 쉽지 않아보이는데….
- 관찰을 하자
- $s_1 \leq s_2,\ e_2 \leq e_1$ 인 전시 $m_1, m_2$가 있다고 하자.
- 이 때, $m_2$ 를 방문하면 자연스럽게 $m_1$을 방문하게 된다!!
- 따라서, $s_1 < s_2, \ e_1 < e_2$인 전시들만을 남길 수 있다.
- 이렇게 하면 $C(j, i) = min(c_{s_i}, \dots, c_{e_j})$ 로 조금 더 단순화가 된다.
- 그런데, 날짜가 생각보다 많지 않지 않나? 저걸 날짜 하나하나에다가 풀어도 되지 않을까?
- 이것도 모노톤 스택으로 구현 가능하다.
- $s_1 \leq s_2,\ e_2 \leq e_1$ 인 전시 $m_1, m_2$가 있다고 하자.
- DP식을 다시 세우자
- $\text{DP}[i]$ = i번째 날까지, 이날 전시를 보고, 이날 볼수있는 전시들까지 모두 보았을때 최소비용
- 전이 식은?
- $\text{DP}[i] = \min\limits_{s_i \leq e_j}(\text{DP}[j]) + c_i$
- 범위를 세그먼트 트리 + 이분 탐색으로 찾아가며 $O(N\log^2N)$ 도 되겠지만, 범위 최솟값이므로 덱 트릭을 이용할 수 있다!
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> M;
rep(i, 1, N+1) cin >> C[i];
exhibits.resize(M);
rep(i, 0, M) cin >> exhibits[i].first >> exhibits[i].second;
// s_i < s_j && e_i < e_j 만 남기기
sort(all(exhibits));
vector<pii> new_exhibits;
stack<pii> stk;
for(auto [s, e]: exhibits){
while(!stk.empty() && stk.top().second >= e) stk.pop();
stk.push({s, e});
}
while(!stk.empty()){
new_exhibits.push_back(stk.top());
stk.pop();
}
reverse(all(new_exhibits));
M = new_exhibits.size();
// 덱 트릭을 이용한 DP 최적화
DP[0] = 0;
deque<pll> dq; // (idx, val)
dq.push_back({0, DP[0]});
int idx = 0, cur = 0;
rep(i, 1, N+1){
if(idx < M && new_exhibits[idx].second < i){
cur = new_exhibits[idx].first;
idx++;
}
while(!dq.empty() && dq.front().first < cur) dq.pop_front();
DP[i] = dq.front().second + C[i];
while(!dq.empty() && dq.back().second >= DP[i]) dq.pop_back();
dq.push_back({i, DP[i]});
}
ll ans = 1e18;
auto [s_last, e_last] = new_exhibits.back();
rep(i, s_last, e_last+1) ans = min(ans, DP[i]);
cout << ans << "\n";
}