[C++] 백준 11993번: Circular Barn (Gold)

문제

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

11993번: Circular Barn (Gold)

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

설명

https://korini.tistory.com/47

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

전에 풀었던 문제와 동일하지만 범위가 다르다 (n: 1,000 -> 100,000)

이전에 풀었던 코드로 돌려보니, 역시나 메모리초과가 나왔다.

가장 적게 움직인 소를 알기 위해 nxn 테이블을 만든 것이 문제였다. (table[i][j]는 i 번째 방에 j만큼 움직인 소의 마리 수)

줄일 수 있는 방법을 고민하다가, n개의 priority queue를 이용해서 소가 있는 경우만 자신이 움직인 거리만큼 표시해서 queue안에 집어 넣는 방식을 생각했다.

그러면 priority queue에서 순서대로 뽑아 다음 방으로 +1 표시한 후 옮기는 방법을 생각했다.

코드 1

#include <string>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    int temp;
    vector<priority_queue<int>> queues;
    for (int i = 0; i < N; i++) {
        scanf("%d", &temp);
        priority_queue<int> q;
        for (int j = 0; j < temp; j++) {
            q.push(0);
        }
        queues.push_back(q);
    }
    
    /*
    for (int i = 0; i < N; i++) {
        printf("%lu", queues[i].size());
    }
    */
    
    for (int i = 0; i < N; i++) {
        // printf("%lu", queues[i].size());
        long unsigned q_size = queues[i].size();
        if (q_size <= 1) continue;
        
        for (int j = 0; j < q_size-1; j++) {
            int dist = -queues[i].top();
            queues[i].pop();
            queues[(i+1)%N].push(-dist-1);
        }
        // printf(" %lu\n", queues[i].size());
    }
    
    for (int i = 0; i < N; i++) {
        // printf("%lu", queues[i].size());
        long unsigned q_size = queues[i].size();
        if (q_size <= 1) continue;
        
        for (int j = 0; j < q_size-1; j++) {
            int dist = -queues[i].top();
            queues[i].pop();
            queues[(i+1)%N].push(-dist-1);
        }
        // printf(" %lu\n", queues[i].size());
    }
  
    long long cnt = 0;
    for (int i = 0; i < N; i++) {
        int dist = queues[i].top();
        cnt += dist * dist;
    }
    printf("%lld", cnt);
    return 0;
}

priority queue에 넣을 떄 마이너스를 붙이는 이유는 c++에서 priority queue는 내림차순이기 때문에 넣을 때 마이너스를 붙이고 뺄 때 마이너스를 다시 붙이면 된다. 이렇게 하기 싫으면 greater<int> 이런 얘들을 넣어줘야하는데 항상 헷갈린다.

 

근데 이 코드도 성공하지만 친구가 이것보다 더 시간을 줄일 수 있는 법을 알려줬다.

위의 코드는 소를 한 칸씩 옮기지만, 실제로는 작은 것을 가장 멀리 보내면 시간을 단축시킬 수 있다는 것이다.

예를 들어, 방에는 무조건 한 마리의 소가 있어야하니, 위의 코드같은 경우에는 i 번째 방에 n마리의 소가 있는 경우 (n-1)마리를 (i+1)번째 방에 보내고, 다시 (i+1)번째 방에 있는 소 중 가장 멀리에서부터 온 소 한마리를 제외하고 다음 방에 보내는데, 이럴 필요 없이 i 번째 방에 있는 n마리 소 중 가장 움직이지 않은 소부터 (i+n-1) 번째 방에 보내고 순서대로 보내서 두 번째로 가장 많이 걸어온 소를 (i+1)에 보내면 된다. 그러면 시간을 단축할 수 있다.

코드 2

#include <string>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    int temp;
    vector<priority_queue<int>> queues;
    for (int i = 0; i < N; i++) {
        scanf("%d", &temp);
        priority_queue<int> q;
        for (int j = 0; j < temp; j++) {
            q.push(0);
        }
        queues.push_back(q);
    }
    
    /*
    for (int i = 0; i < N; i++) {
        printf("%lu", queues[i].size());
    }
    */
    
    for (int i = 0; i < N; i++) {
        // printf("%lu", queues[i].size());
        long unsigned q_size = queues[i].size();
        if (q_size <= 1) continue;
        
        for (int j = 0; j < q_size-1; j++) {
            int dist = -queues[i].top();
            queues[i].pop();
            queues[(i+q_size-1-j)%N].push(-dist-q_size+1+j);
        }
        // printf(" %lu\n", queues[i].size());
    }
    
    for (int i = 0; i < N; i++) {
        // printf("%lu", queues[i].size());
        long unsigned q_size = queues[i].size();
        if (q_size <= 1) continue;
        
        for (int j = 0; j < q_size-1; j++) {
            int dist = -queues[i].top();
            queues[i].pop();
            queues[(i+q_size-1-j)%N].push(-dist-q_size+1+j);
        }
        // printf(" %lu\n", queues[i].size());
    }
  
    long long cnt = 0;
    for (int i = 0; i < N; i++) {
        int dist = queues[i].top();
        cnt += dist * dist;
    }
    printf("%lld", cnt);
    return 0;
}

결과

시간과 메모리 부분에서 엄청나게 단축되었음을 알 수 있다.