BOJ#11993 Circular Barn (Gold)

조금 생각해야하는 그리디다.

문제에 있는 예제는 그리기 힘드니, input : 7 2 0 2 0 3 0 0 ans : 15 인 예제를 사용해서 동작을 이해해보자. 

 

[접근]

편의상 입력을 거꾸로 받아 반시계 방향으로 문제를 살펴보았다. 배열의 인덱스가 증가하는 순으로 관리할 수 있어 구현이 편해진다. 배열의 인덱스가 의미하는 것은 Room 이고, 배열에 들어있는 값이 의미하는 것은 소의 개체수이다. 

 

소가 방을 찾아가는게 무언가 그리디하다는 점을 느낄 수 있어서 다음과 같은 동작을 생각해보하면 답을 구할 수 있을 것 같다는 느낌이 든다. 자신의 오른쪽에 있는 (자신을 포함하여) 가장 가까운 소를 찾아 자신의 방에 넣는다.

 

문제에 접근할 때는 원형배열에 흔히 쓰는 기법인 인덱스를 2배 늘려주는 식으로 생각했으나, 풀다보면 배열의 크기를 n까지만 잡아도 된다는 것을 알 수 있다.

 

 

다만 이렇게 하면 답은 1 + 1 + 4 + 25 = 31로 오답이 된다. 자신의 인덱스에 있는 소를, Room에 그대로 넣어주지 않고, 이동시키는 게 이득일 수도 있기 때문이다.

 

어떻게 해야할까 고민해보자.

Sum을 소들의 합 (prefix sum) 이라 하고, i를 현재 보는 배열의 인덱스(Room)라고 하자. 뒤로 이동해야하는 소는 Sum - i 마리라는 것을 알 수 있다. 인덱스 하나당 소가 한 마리씩 대응되고, 남은 소들은 뒤로 미루어지기 때문이다.

 

 

그렇다면, sum - i가 최대가 되는 지점의 다음 지점을 시작점으로 잡으면 더 이상 뒤로 미루어지는 소가 없기 때문에, 처음 생각한 기법을 적용시킬 수 있다. 이제 구현을 알아보자 !

 

[구현]

반시계방향이 아무래도 익숙하니 입력을 뒤집어서 받자.

 

for(ll i=1;i<=n;i++) cin>>ipt[n+1-i];

 

어떤 점에서 sum - i 를 max로 하는 i값을 찾아 시작점으로 지정해주자

 

ll s = 1, sum = 0, compare = -1e9;
for (ll i = 1; i <= n; i++) {
  sum += ipt[i];
  if (sum - i >= compare) {
    s = i + 1;
    compare = sum - i;
    if (i == n) s = 1;
  }
}

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, ipt[1<<17], ans=0;
queue<ll> q;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>ipt[n+1-i];
    ll s=1,sum=0,compare=-1e9;
    for(ll i=1;i<=n;i++){
        sum+=ipt[i];
        if(sum-i>=compare){
            s=i+1; compare=sum-i;
            if(i==n) s=1;
        }
    }
    for(ll i=s;i<=n;i++){
        while(ipt[i]--) q.push(i-s+1);
    }
    for(ll i=1;i<s;i++){
        while(ipt[i]--) q.push(i+1+n-s);
    }
    for(ll i=1;i<=n;i++){
        ll now=q.front(); q.pop();
        ans+=(now-i)*(now-i);
        now=i;
    }
    cout<<ans;
}