본문 바로가기

PS

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

 

[구현]

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

 

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

 

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

 

1
2
3
4
5
6
7
8
9
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;
  }
}
cs

 

시작점을 기준으로 queue에 넣어주자. 작점 앞에 있는 소들은 인덱스에 +n을 해서 넣어주면 된다.

 

 
1
2
3
4
5
6
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);
}
cs

 

 

그 뒤로는 s부터 시작해서 s+n-1까지의 Room에 q.front()에 있는 소를 넣어주면 된다. 소는 n마리이고 방도 n개이며, q에서 하나씩만 꺼내므로, 반복문이 끝날 때에는 q가 비고 결국 모든 소가 자신의 방을 찾게 된다.

 

전체 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}
cs

 

'PS' 카테고리의 다른 글

Google Code Jam 2020 Round 1A 후기  (0) 2020.04.24
Kick Start Round A 2020 후기  (0) 2020.03.23
BOJ#11993 Circular Barn (Gold)  (0) 2020.03.10
USACO 2016 February Gold 업솔빙  (0) 2020.03.09
1일 1알고 하는 글 - 실패  (0) 2020.02.26
USACO 2020 January Gold 업솔빙 후기  (0) 2020.02.16

태그