[BOJ] 21558: 전쟁 준비하기

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

BOJ - 전쟁 준비하기

문제 유형 : 구현, 수학, 그리디

문제 난이도 : Silver I

 

문제

이번에 폴리매스 왕국은 이웃 나라인 사이언스보드를 정복하기 위해 전쟁을 치르려고 합니다. 당신은 전쟁에서 사용할 방진을 짜 달라는 부탁을 받아 방진을 연구하고 있습니다.

전쟁 지역의 지형상 가장 효율적인 방진은 직사각형 구조일 것으로 보입니다.

즉 X행Y열의 직사각형을 정확히 XY명의 병사가 채우고 있는 형태를 말합니다. 병사의 수가 정확히 떨어지지 않아 몇 명이 남거나 부족한 경우에는 이러한 방진을 짤 수 없습니다.

폴리매스 문명은 예전에도 강력한 군사력으로 주변의 약소국을 다수 복속시켰으므로, 군대에도 서로 다른
N개의 민족이 섞여 있습니다. 특히, 이번 전쟁에 참가하게 될 병사들 중
i번째 민족 출신인 병사는 정확히
A_i명인 것으로 집계되었습니다.

출신 민족에 따라 계급이 존재하기 때문에, 병사들의 위치를 아무렇게나 정할 수 없습니다. 특히
i<j일 때 i번째 민족 출신인 병사는 항상 j번째 민족 출신인 병사보다 앞에 서야 합니다.

이 때 a행b열에 위치한 병사가 a'행b'열에 위치한 병사보다 앞에 선다는 말은 다음 둘 중 하나가 성립함을 의미합니다.

 
a<a
a=a'이고 b<b' 

 

그러나 이 방식에는 약간의 문제가 있는데, 서로 다른 민족인 병사끼리 양옆으로 인접해 있다면 싸움이 벌어질 것입니다. 이 때

a행 b열에 위치한 병사와 a'행 b'열에 위치한 병사가 양옆으로 인접해 있다는 말은 a=a'이고 |b-b'|=1임을 뜻합니다.

당신이 이러한 문제점을 보고하자, 왕국의 육군 장교들은 싸움을 막기 위해 평화의 돌을 사용하기로 했습니다. 평화의 돌의 힘을 사용하면 서로 다른 민족인 병사가 인접해 있더라도 싸움이 나는 것을 막을 수 있지만, 한 개의 돌 당 하나의 싸움밖에 막을 수 없습니다.

즉 평화의 돌을 k개 가지고 있다면 민족이 다르고 서로 인접한 병사의 쌍이 k쌍 이하여야 싸움이 일어나지 않는 것입니다.

군대의 장교들은 방진이 옆으로 넓을수록, 즉 Y가 최대한 클수록 군대가 강하다고 생각합니다. 따라서 당신은 위 조건을 만족하는 방진 중 가장 큰 Y값을 가지는 방진을 찾아내야 합니다. 그러나 평화의 돌에 관련된 정보는 왕국의 기밀 사항이기 때문에, 당신은 정확히 몇 개의 평화의 돌이 있는지 알지 못합니다.

 

따라서 당신은 0 <= k <= N-1인 모든 정수 k에 대해서 가능한 Y의 최댓값을 모두 구하기로 했습니다.

 

입력

첫 줄에는 민족의 수
N이 주어집니다.

다음 줄에는 각 민족의 병사 수 A_1, A_2, ..., A_N이 주어집니다.

 

출력

첫 줄에
0 <= k <= N-1인 모든 정수 k에 대해 가능한 Y의 최댓값을 각각 공백으로 구분하여 출력합니다.

 

제한 

1 <= N <= 10^3$
 1 <= A_i <= 10^6
 
M <= 10^6

(단, M=A_1+A_2+ ... +A_N)

 

풀이

Y값이 될 수 있는 수들은, 바로 모든 병사의 합의 약수이다.

즉, 가능한 Y값 후보들을 미리 구할 수 있다.

 

그리고, 병사들을 민족 번호 순으로 나열하여 병사들을 일렬로 나열시킨다. 이러면 모의 배치를 편하게 할 수 있다.

각 가능한 Y값 후보들에 대해서:

  행우선으로 배치한다. 그러다 같은 행에서 서로 다른 민족들의 병사들이 인접하게 되면, 싸움의 수를 누적시킨다.

  이를 각각 [{싸움수, Y값}]꼴로 저장해놓는다.

 

각각의 k값(0 ~ n-1)마다 최대의 Y값을 저장시킨다. 이를 max_Y[k]배열에 담아놓는다.

 

출력해주면 된다.

 

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> soldiers(n);
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> soldiers[i];
        sum += soldiers[i];
    }

    vector<int> divisors;
    for (int i = 1; i * i <= sum; ++i)
    {
        if (sum % i == 0)
        {
            divisors.push_back(i);
            if (i != sum / i)
                divisors.push_back(sum / i);
        }
    }
    sort(divisors.begin(), divisors.end(), greater<int>());

    vector<int> group_list;
    for (int i = 0; i < n; ++i)
    {
        group_list.insert(group_list.end(), soldiers[i], i);
    }

    vector<pair<int, int>> fights_Y;
    for (int Y : divisors)
    {
        int fights = 0;
        int M = sum;
        int H = M / Y;
        for (int r = 0; r < H; ++r)
        {
            for (int c = 0; c < Y - 1; ++c)
            {
                int idx1 = r * Y + c;
                int idx2 = idx1 + 1;
                if (group_list[idx1] != group_list[idx2])
                    fights++;
            }
        }
        fights_Y.push_back({fights, Y});
    }

    vector<int> max_Y(n, 0);
    for (int k = 0; k < n; ++k)
        max_Y[k] = 0;

    for (auto &fy : fights_Y)
    {
        int fights = fy.first;
        int Y = fy.second;
        for (int k = fights; k < n; ++k)
        {
            max_Y[k] = max(max_Y[k], Y);
        }
    }

    for (int k = 0; k < n; ++k)
    {
        cout << max_Y[k] << " ";
    }
    cout << "\n";

    return 0;
}