오늘 뭐했지

https://boj.ma/23889/t

돌이 굴러가는 위치들이 주어지고, 세울 수 있는 벽의 개수가 주어질 때 벽을 적절한 위치에 세워 파괴되는 모래성의 개수를 최소로 하고 싶습니다.

완전탐색부터 생각해 보면

주어지는 N개의 위치에 대해 M개의 벽을 놓는 모든 경우의 수에 대해 해 보는 것입니다.

$_{N} C_{M}$ 가지의 경우에 대해 돌을 놔보고, 그때마다 계산을 해주면? 당연히 시간초과입니다.

최적화를 생각해 봅시다

모든 위치에 벽을 놔보는 것이 오래 걸리니 벽을 놓지 않아도 되는 위치에 대해 생각해 봅시다.

저는 처음에 주어지는 돌이 굴러가기 시작하는 위치에만 벽을 놓으면 된다고 생각했습니다.

당연하게도 돌이 굴러가다가 막는 것보다 애초에 돌이 구르지 못하게 하는 것이 더 이득이기 때문입니다.

하지만 돌의 개수 K 또한 최대 N까지 가능하므로 돌의 위치에만 벽을 세워본다 하더라도 시간초과가 날 것입니다.

이제, 벽을 놓지 않아도 되는 돌의 위치에 대해 생각해 봅시다.

예를 들어 입력 예제가 다음과 같이

10 1 2
1 2 3 4 5 6 7 8 9 10
1 10

이런 형태라면

벽은 하나만 놓을 수 있고 돌이 굴러가기 시작하는 위치는 1, 10이므로

1번 위치에 벽을 세우면 10만큼의 모래성이 파괴되지만 10에 설치하게 되면 45만큼의 모래성이 파괴됩니다.

이것을 통해

각 돌마다 벽이 없을 때 파괴하는 모래성의 개수를 알고 있다면, 가장 많이 파괴하는 돌부터 막는 게 최적일 것이라고 생각했습니다.

따라서 돌마다 파괴하는 모래성의 개수를 전처리하여 구하고, 정렬하여 낮은 인덱스 순서대로 출력하면 됩니다.

코드 (c++)

#include <bits/stdc++.h>

#define endl "\n"
#define NM 100101
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 1000000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 i128;
using namespace std;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> arr(n + 1), stone(k + 1), psum(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1 ;i <= k; i++) cin >> stone[i];
    for (int i = 1; i <= n; i++) psum[i] = psum[i - 1] + arr[i];
    vector<pii> v;
    for (int i = 1 ; i < k; i++){
        v.push_back({psum[stone[i + 1] - 1] - psum[stone[i] - 1], stone[i]});
    }
    v.push_back({psum[n] - psum[stone.back() - 1], stone.back()});

    auto comp = [&](pii a, pii b) -> bool{
        if (a.X == b.X) return a.Y < b.Y;
        return a.X > b.X;
    };

    sort(all(v), comp);

    vector<int> ans;

    int cnt = min(m, k);
    for (int i = 0 ; i < cnt; i++){
        ans.push_back(v[i].Y);
    }
    sort(all(ans));

    for (auto i : ans) cout << i << endl;

    return 0;
}