[BOJ 22516 // C++] Magical Girl Sayaka-chan

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 22516번 문제인 Magical Girl Sayaka-chan이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/22516

 

\(K\)의 나열에서 증가했다가 감소했다가 다시 증가하는 부분이 있다면 이 부분을 단조증가 또는 단조감소의 형태로 순서를 바꿔 항상 이 부분의 반발력을 유지 또는 줄일 수 있음을 관찰하자. 이러한 관찰을 이용하면 \(K\)의 나열은 증가와 감소의 변화를 최소화하는 방식으로 나열된 경우에서 반발력이 최소가 되는 경우 중 하나를 항상 찾을 수 있음을 알 수 있다.

 

증가와 감소의 변화가 최소화되는 나열방식은 가장 작은 \(K\)에서 가장 큰 \(K\)까지 단조증가하면서 이동한 뒤 이 과정에서 사용하지 않은 모든 \(K\)를 단조감소하게 나열하는 것이다. 이는 모든 \(K\)값을 다 사용하면서 가장 작은 \(K\)에서 가장 큰 \(K\)까지 도달하는 두 개의 수열을 구성하는 것으로도 생각할 수 있으며, 여기까지 생각을 해냈다면 남은 문제는 경찰차 DP가 됨을 어렵지 않게 알 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

ll ans = 0x3f3f3f3f3f3f3f3f;
int N, M, L;
int A[2001]; ll P[100001];
ll dp[2001][2001];

ll func(ll i, ll j) {
    if (i < j) swap(i, j);
    if (dp[i][j] < 0x3f3f3f3f3f3f3f3f) return dp[i][j];
    ll &ret = dp[i][j];
    if (i == j + 1) {
        for (int k = 0; k < j; k++) ret = min(ret, func(j, k) + (P[A[i]] - P[A[k] - 1]) / L);
    }
    else ret = func(i - 1, j) + (P[A[i]] - P[A[i - 1] - 1]) / L;
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> L;
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A, A + N);
    for (int i = 1; i <= M; i++) cin >> P[i], P[i] += P[i - 1];

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    dp[1][0] = (P[A[1]] - P[A[0] - 1]) / L;
    for (int k = 0; k + 1 < N; k++) ans = min(ans, func(N - 1, k) + (P[A[N - 1]] - P[A[k] - 1]) / L);
    cout << ans;
}