조금 생각해야하는 그리디다.
문제에 있는 예제는 그리기 힘드니, input : 7 2 0 2 0 3 0 0 ans : 15 인 예제를 사용해서 동작을 이해해보자.
[접근]
편의상 입력을 거꾸로 받아 반시계 방향으로 문제를 살펴보았다. 배열의 인덱스가 증가하는 순으로 관리할 수 있어 구현이 편해진다. 배열의 인덱스가 의미하는 것은 Room 이고, 배열에 들어있는 값이 의미하는 것은 소의 개체수이다.
소가 방을 찾아가는게 무언가 그리디하다는 점을 느낄 수 있어서 다음과 같은 동작을 생각해보하면 답을 구할 수 있을 것 같다는 느낌이 든다. 자신의 오른쪽에 있는 (자신을 포함하여) 가장 가까운 소를 찾아 자신의 방에 넣는다.
다만 이렇게 하면 답은 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 |
USACO 2016 February Gold 업솔빙 (0) | 2020.03.09 |
1일 1알고 하는 글 - 실패 (0) | 2020.02.26 |
USACO 2020 January Gold 업솔빙 후기 (0) | 2020.02.16 |