BOJ 11993 : Circular Barn (Gold)

알고리즘

greedy, dp

시간복잡도

$O(N)$

풀이

$a<b<c<d$일 때, $(a, b)$에서 $(c, d)$로 옮겨야 한다면,
$(a->c, b->d)$가 $(a->d, b->c)$보다 항상 비용이 작음이 증명된다.
따라서 절대 소가 밀릴 일이 없는 지점에서 시계 방향으로 돌 때
가장 가까운 0으로부터 순차적으로 밀어주면 된다.

dp를 통해 가장 많이 밀린 지점을 구할 수 있으며,
$O(N)$으로 끝에 있는 0부터 채워주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int N, a[100005], dp[100005];
ll ans;

ll add(ll b, ll n)
{
    ll r = 0;
    for (ll i = 0; i < n; i++) r += (b-i)*(b-i);
    return r;
}

int main()
{
    cin>>N; for (int i = 1; i <= N; i++) cin>>a[i];
    for (int i = N; i >= 1; i--) dp[i] = dp[i+1] + a[i] - 1;
    int mx = -100000, p;
    for (int i = N; i >= 1; i--)
        if (dp[i] >= mx)
            {mx = dp[i]; p = i;}
    if (!mx) {cout<<0; return 0;}
    for (int i = 1; i <= N; i++)
        if (!a[p-i < 1 ? p-i+N : p-i])
            {p = p-i < 1 ? p-i+N : p-i; break;}
    int num0 = 0;
    for (int i = 0; i < N; i++) {
        int now = p-i < 1 ? p-i+N : p-i;
        if (!a[now]) {num0++; continue;}
        ans += add(num0, a[now]);
        num0 -= a[now]-1;
    }
    cout<<ans; return 0;
}