1006 - 습격기 초라기

2024. 4. 5. 21:28ㆍAlgorithm/Baekjoon & Solved.ac

Part 1

일단 원형이 아닌 직사각형의 형태의 문제라고 가정하고 풀기

1번째 구역에서 가능한 경우의 수

1
2

다음과 같이 서로 다른 두개의 특수소대를 배치하는 것을 연산 a라고 정의

1
1

다음과 같이 한개의 특수소대를 배치하는 것을 연산 b라고 정의

2번째 구역에서 가능한 경우의 수

구역 1에서 연산 a를 수행 했을 경우

1	3
2	4

1	3
2	3

연산 a / b를 또 다시 수행

1	->
2	3

다음과 같이 위쪽의 특수부대를 왼쪽으로 연이어 배치하는 것을 연산 c라고 정의

1	3
2	->

다음과 같이 아래쪽의 특수부대를 오른쪽으로 연이어 배치하는 것을 연산 d라고 정의

1	->
2	->

두 개의 특수부대를 모두 연이어 배치하는 것을 연산 e라고 정의

구역 1에서 연산 b를 수행 했을 경우

이 경우 오른쪽으로 전진 배치하는 것이 불가능하므로, 연산 a 및 b 만 수행 가능

3번째 구역 이후

이전에 연산 a를 수행 했을 경우

이 경우 연산 a~e를 모두 수행 가능

이전에 연산 b를 수행 했을 경우

가로로 부대가 배치된 상태이므로, 연산 a와 b로 새로 부대를 배치하는 것만이 가능

이전에 연산 c를 수행 했을 경우

위쪽의 부대는 이미 연이어 배치한 상황이므로, 새로 배치하거나 / 아래쪽의 부대를 연이어 배치하는 것만이 가능

따라서, 연산 a, b, d 수행 가능

이전에 연산 d를 수행 했을 경우

아래쪽의 부대는 이미 연이어 배치한 상황이므로, 새로 배치하거나 / 위쪽의 부대를 연이어 배치하는 것만이 가능

따라서, 연산 a, b, c 수행 가능

이전에 연산 e를 수행 했을 경우

b와 동일하게, 어떠한 방식으로도 연이어 배치가 불가능하므로, 새로 부대를 배치해야함. 따라서 연산 a, b만이 수행 가능

여기까지 정리

flowchart LR;
A ---> Ra[A, B, C, D, E]
B ---> Rb[A, B]
C ---> Rc[A, B, D]
D ---> Rd[A, B, C]
E ---> Re[A, B]

Part 2

원형을 분리해서 풀기

첫번째 연산을 a/b/c/d/e 중 하나로 두고 시작

a/b일 경우 -> 마지막 연산은 어떠한 것이든 가능
c일 경우 -> a/d 가능
d일 경우 -> a/c 가능
e일 경우 -> a만 가능

이 것은 위의 표를 역으로 생각 했을 때의 결과이기도 하다.

따라서, a~e 연산으로 시작하여, 정해진 연산으로 끝나는 경우의 수를 계산하는 것과 동일하다.

이를 이제 dp를 이용하여 구하면 된다.

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

#define INT_MAX 2147483647

using namespace std;

void test()
{
    int n, w;

    cin >> n >> w;

    vector<vector<int>> data(2, vector<int>(n));

    for (int i = 0;i < 2;++i)
    {
        for (int j = 0;j < n;++j)
        {
            cin >> data[i][j];
        }
    }

    if (n == 1)
    {
        if (data[0][0] + data[1][0] <= w) cout << "1" << endl;
        else cout << "2" << endl;
        return;
    }

    vector<vector<int>> minArmy(5, vector<int>(n));
    vector<int> cost = { 2, 1, 1, 1, 0 };
    vector<vector<int>> targetIndex = {
        {0,1,2,3,4},
        {0,1,2,3,4},
        {0,3},
        {0,2},
        {0}
    };
    vector<function<bool(int)>> isAvailable = {
        [w, data, minArmy](int index) {
            return data[0][index] <= w && data[1][index] <= w;
        },

        [w, data, minArmy](int index) {
            return data[0][index] + data[1][index] <= w;
        },

        [n, w, data, minArmy](int index) {
            int prevIndex = index - 1;
            if (prevIndex < 0) prevIndex += n;

            return data[0][prevIndex] + data[0][index] <= w && data[1][index] <= w;
        },

        [n, w, data, minArmy](int index) {
            int prevIndex = index - 1;
            if (prevIndex < 0) prevIndex += n;

            return data[1][prevIndex] + data[1][index] <= w && data[0][index] <= w;
        },

        [n, w, data, minArmy](int index) {
            int prevIndex = index - 1;
            if (prevIndex < 0) prevIndex += n;

            return data[0][prevIndex] + data[0][index] <= w && data[1][prevIndex] + data[1][index] <= w;
        }
    };

    int min = INT_MAX;
    for (int currentOperation = 0; currentOperation < 5; ++currentOperation)
    {
        if (!isAvailable[currentOperation](0))
            continue;

        for (int i = 0; i < 5; ++i)
        {
            if (currentOperation == i)
                minArmy[i][0] = cost[currentOperation];
            else
                minArmy[i][0] = INT_MAX;
        }

        for (int i = 1; i < n-1; ++i)
        {
            for (int operation = 0; operation < 5; ++operation)
            {
                if (isAvailable[operation](i))
                {
                    vector<int> minList;

                    for (auto&& target : targetIndex[operation])
                    {
                        minList.push_back(minArmy[target][i-1]);
                    }

                    auto min = *min_element(minList.begin(), minList.end());

                    if (min == INT_MAX)
                    {
                        minArmy[operation][i] = INT_MAX;
                    }
                    else
                    {
                        minArmy[operation][i] = min + cost[operation];
                    }

                }
                else
                {
                    minArmy[operation][i] = INT_MAX;
                }
            }
        }

        for (int operation = 0; operation < 5; ++operation)
        {
            vector<int> availableOperation = targetIndex[currentOperation];
            auto findResult = find(availableOperation.begin(), availableOperation.end(), operation);
            if (isAvailable[operation](n-1) && findResult != availableOperation.end())
            {
                vector<int> minList;

                for (auto&& target : targetIndex[operation])
                {
                    minList.push_back(minArmy[target][n - 2]);
                }

                auto min = *min_element(minList.begin(), minList.end());

                if (min == INT_MAX)
                {
                    minArmy[operation][n-1] = INT_MAX;
                }
                else
                {
                    minArmy[operation][n-1] = min + cost[operation];
                }
            }
            else
            {
                minArmy[operation][n - 1] = INT_MAX;
            }
        }

        for (int i = 0;i < 5;++i)
        {
            if (min > minArmy[i][n - 1])
                min = minArmy[i][n - 1];
        }
    }

    cout << min << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;

    cin >> t;

    for (int i = 0;i < t;++i)
    {
        test();
    }


    return 0;
}

ancy_dev