[C++] 백준 11996번: Circular Barn (Silver)

> 문제

https://www.acmicpc.net/problem/11996

11996번: Circular Barn (Silver)

간단하게, n 개의 공간과 n 마리의 소가 있을 때 각 방에 1마리의 소를 넣는 문제이다. 공간은 순환 구조로 되어있고, 소는 시계 방향으로만 이동이 가능하다. 현재 각 방에 소가 몇 마리 있는지 정보가 주어지며, 소가 d 이동할 때 d^2의 에너지가 소모되는데 에너지의 합을 최소로 하는 경우의 에너지 값을 구하면 된다.

문제를 풀기 위해 기본적으로 알아야할 것은 '소를 이동시킬 때 어떻게 할 것인가'이다.

위의 그림의 예시 상황에서 0인 공간을 채운다고할 때, 어디의 소를 가져올 것이냐에 대한 고민을 하게 된다. 위의 예시에서는 시계 반대방향으로 소가 있는 가장 가까운 곳은 b만큼 떨어져 있고 그 곳에는 한 마리의 소가 있다. 다음으로 소가 있는 공간은 (a+b)만큼 떨어져 있다. 이 때, b만큼 떨어진 곳에서 소를 가져올수도 있고, (a+b)만큼 떨어진 곳에서 소를 가져올 수 있다. 만약 b만큼 떨어진 곳의 소를 가져올 경우 해당 공간 또한 0이 되어버려 또 시계 반대 방향으로 가장 가까운 곳에 위치한 소를 가져와야한다. 반면, (a+b)에서 가져오는 경우 한 마리 이상이 있으므로 한 마리만 움직이면 된다. 하지만 실제로 계산해보면, 전자는 a만큼을 이동하는 소 한마리와 b만큼 이동하는 소 한마리이므로 (a^2 + b^2)만큼의 에너지가 발생하지만, 후자의 경우 (a+b)^2만큼의 에너지가 발생하여 두 마리를 옮기는 쪽이 에너지측면에서 이득이 된다. 즉, 무조건 가장 가까운 0이 아닌 곳에서 가져온다고 생각하면된다.

0을 채워야하는 대상으로 볼수도 있지만, 다시 생각해보면 두 마리 이상이 있는 공간에서 소를 모두 다른 곳으로 보내면 된다고 생각했다. 주의할 점은 소를 이동시켜야할 때 덜 움직인 소를 움직이게 해야한다. 덜 움직인 소를 알기 위해 소가 얼마나 이동했는지에 대한 정보 저장도 필요하다.

 

#include <string>
#include <vector>

using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    vector<int> vec(N, 0);
    for (int i = 0; i < N; i++) {
        scanf("%d", &vec[i]);
    }
    
    vector<vector<int>> table(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++) {
        table[0][i] = vec[i];
    }

    for (int i = 0; i < N; i++) {
        if (vec[i] <= 1) continue;
        
        for (int j = 0; j < N; j++) {
            int temp = table[j][i] - 1;  // table[j][i] represents the number of cows which walk through j distance at the i-th place
            table[j][i] = 1;
            vec[i] -= temp;
            table[j+1][(i+1)%N] += temp;
            vec[(i+1)%N] += temp;
            if (vec[i] == 1) {
                break;
            } else {
                table[j][i] = 0;
                vec[i]--;
                table[j+1][(i+1)%N]++;
                vec[(i+1)%N]++;
            }
                
        }
    }

    for (int i = 0; i < N; i++) {
        if (vec[i] == 1) continue;
        
        for (int j = 0; j < N; j++) {
            int temp = table[j][i] - 1;  // table[j][i] represents the number of cows which walk through j distance at the i-th place
            table[j][i] = 1;
            vec[i] -= temp;
            table[j+1][(i+1)%N] += temp;
            vec[(i+1)%N] += temp;
            
            if (vec[i] == 1) {
                break;
            } else {
                table[j][i] = 0;
                vec[i]--;
                table[j+1][(i+1)%N]++;
                vec[(i+1)%N]++;
            }
            
        }
    }

    int cnt = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (table[i][j]==0) continue; 
            cnt += i * i;
        }
    }
    
    printf("%d", cnt);

    return 0;
}

N크기의 공간이 주어지면 vec에 저장하고, NxN 크기의 벡터(table)를 생성한다. table[j][i]는 i번째 공간에 j만큼 이동한 소의 개수를 의미한다. 0번째 행에는 이동하지 않은 소를 의미하므로 주어진 vec 값으로 초기화해준다. vec을 돌면서 한 마리 이상의 소가 있는 공간은 한 마리를 제외하고 모두 시계방향으로 한 칸 옮겨준다. 즉 table[j][i] 값을 table[j+1][i+1]로 옮겨준다. 주의할 점은 한 마리를 제외하고 보내야한다는 것이고, 이동을 가장 안한 소부터 보내야한다는 것이다. 추가로 modulo를 쓴 이유는 순환 구조이기 때문에 마지막에 있던 소를 다시 첫 번째 공간에 보내기 위해서이다. 시작점을 따로 찾지 않고 시작했기 때문에 순환 구조에서 2번을 순환하게 하여 모든 소가 각 방에 들어갈 수 있게 하였다.

> 결과