백준 11996 Circular Barn (USACO February 2016 Silver 1번)

문제 링크: https://www.acmicpc.net/problem/11996

11996번: Circular Barn (Silver)

비어있는 방을 찾아서 반시계 방향으로 제일 가까운 소로 채워넣으면 됨. 소를 옮길때마다 거리배열로 업데이트해야함.

예시

1 0 0 2 0 0 1 2 2 2          

1 0 0 1 0 1 1 2 2 2          0 0 0 0 0 2 0 0 0 0 

1 0 0 0 1 1 1 2 2 2          0 0 0 0 1 2 0 0 0 0

0 0 0 1 1 1 1 2 2 2          0 0 0 3 1 2 0 0 0 0 

0 0 1 1 1 1 1 2 2 1          0 0 3 3 1 2 0 0 0 0

0 1 1 1 1 1 1 2 2 0          0 2 3 3 1 2 0 0 0 0

0 1 1 1 1 1 1 2 1 1          0 2 3 3 1 2 0 0 0 1

1 1 1 1 1 1 1 2 1 0          2 2 3 3 1 2 0 0 0 0

1 1 1 1 1 1 1 2 0 1          2 2 3 3 1 2 0 0 0 1

1 1 1 1 1 1 1 1 1 1          2 2 3 3 1 2 0 0 1 1

방배열                          거리배열

#include <bits/stdc++.h>
using namespace std;
 
int n, room[1001], d[1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) cin >> room[i];
 
    while(1) {
        bool done = true;
        int to = 0;
        for(int i = 0; i < n; i++) {
            if(room[i] == 0) {
                to = i;
                done = false;
            }
        }
        if(done) break;
 
        int from = to;
        int dist = 0;
        while(1) {
            if(room[from] != 0) break;
            if(from == 0)
                from = n;
            from--;
            dist++;
        }
        room[from]--;
        room[to]++;
        d[to] += dist + d[from];
        d[from] = 0;
    }
 
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += d[i] * d[i];
    cout << ans << '\n';
    return 0;
}