어항 정리

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

23291번: 어항 정리

 

빡 구현 문제

문제를 읽으면서 쭉 따라가보자.

 

제한조건을 보면

숫자가 매우 작고 시간도 넉넉하다

O(N^2) 충분히 될 것 같다.

(다른 쓸 알고리즘이 없기도 하다.)

 

다른 블로그들 코드 보면

배열 돌리기를 사용하던데

나는 그냥 직관적으로 구현을 했다.

 

1. 틀 짜기

우선 구조체를 만들었다.

fishbowl 구조체는

cnt -> 위로 올라가는 어항 개수

arr -> 물고기 수

 

어항이 4개라면

 

5 10 8 9 -> 물고기 수

1  2  3 4 -> 어항 구조체 배열 idx

 

이동을 한다면 어항 구조체 배열의 arr에

push_back()을 해주었다.

예를 들어,

어항 idx 1을 2에 올린다고 하면

1의 arr.clear(), cnt = 0 만들고

 

5

10  8   9

2    3   4  -> 어항 구조체 배열 idx

 

이렇게 된다.

 

이러면 직관적으로

배열 돌리기를 할 필요없이

문제를 이해한다음

인덱스 관리만 해서

vector을 받아주고

다시 주렁주렁 달아주는 방식으로

빡 구현을 하면 된다.

내 코드에서는 전반과 후반으로 나누어서 구현을 했다.

복구하는 것도 원리는 동일하다.

벡터를 받아서 

rbegin()을 하든, 인덱스르 뒤에서 부터 받아서

바꾸면 된다. 

 

2. move_fish

이걸 보드에 옮기면

O(N^2)이 되니까

처음에는 보드에 안옮기고 그냥

구조체에서 하려고 했는데..

너무 복잡해졌다.

 

그래서 그냥 d_board[][]를 만들어서

fishbowl 구조체 배열의 arr를 다 복사해준뒤

이차원 배열에 바뀔 d 값을 저장해주었다.

그리고 값을 바꿔주면 끝.

 

3. 정답 구하기 및 제일 적은 어항에 한 마리 넣어주기

이거는 O(N) 말고는 안 떠오른다.

min_element를 쓰는 블로그도 봤지만

그것도 결국 O(N)으로 구하는 것이기 때문에

그냥 for문 돌렸다.

 

그냥 min 구해서 벡터에 최솟값 인덱스를 저장하고

최솟값 인덱스의 fishbowl 구조체 배열 arr에 +1을 해주면 된다.

 

<소스 코드>

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct info {
    int cnt;
    vector<int> arr;
};
 
info fishbowl[104];
int n, k;
int chk[104];
vector<int> m_idx;
 
void init()
{
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        cin >> tmp;
 
        fishbowl[i].cnt = 1;
        fishbowl[i].arr.push_back(tmp);    
        chk[i] = tmp;
    }
}
 
void add()
{
    m_idx.clear();
    int mn = 10001;
    for (int i = 1; i <= n; i++)
    {
        if (chk[i] < mn)
            mn = chk[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (chk[i] == mn)
            m_idx.push_back(i);
    }
 
    for (int i = 0; i < m_idx.size(); i++)
    {
        fishbowl[m_idx[i]].arr[0]++;
    }
}
 
bool check()
{
    int mx = 0;
    int mn = 10001;
    for (int i = 1; i <= n; i++)
    {
        chk[i] = fishbowl[i].arr[0];
        if (chk[i] > mx)
            mx = chk[i];
        if (chk[i] < mn)
            mn = chk[i];
    }
 
    if ((mx - mn) <= k)
        return true;
    else
        return false;
}
 
int is_one;
int not_one;
 
int d_board[104][104];
void move_fish()
{
    memset(d_board, 0, sizeof(d_board));
    int start = not_one;
 
    while (fishbowl[start].cnt != 0)
    {
        start--;
    }
    
    start += 1;
 
    // 이제 출발 할 수 있다.
    for (int i = start; i <= n; i++)
    {
        for (int j = 0; j < fishbowl[i].arr.size(); j++)
        {
            int genkai = fishbowl[i].arr.size() - 1;
            int gijun_fish = fishbowl[i].arr[j];
 
            // 네 방향 차를 더하자
            if (j != 0) {
                if (((gijun_fish - fishbowl[i].arr[j - 1]) / 5) != 0)
                {
                    if (((gijun_fish - fishbowl[i].arr[j - 1]) / 5) < 0)
                    {
                        d_board[i][j] += ((((gijun_fish - fishbowl[i].arr[j - 1]) * -1) / 5) * -1);
                    }
                    else
                    {
                        d_board[i][j] += ((gijun_fish - fishbowl[i].arr[j - 1]) / 5);
                    }
                }
            }
            if (j != genkai) {
                if (((gijun_fish - fishbowl[i].arr[j + 1]) / 5) != 0)
                {
                    if (((gijun_fish - fishbowl[i].arr[j + 1]) / 5) < 0)
                    {
                        d_board[i][j] += ((((gijun_fish - fishbowl[i].arr[j + 1]) * -1) / 5) *-1);
                    }
                    else
                        d_board[i][j] += ((gijun_fish - fishbowl[i].arr[j + 1]) / 5);
                }
            }
 
            if (i != start)
            {
                auto& v = fishbowl[i - 1].arr;
                if (v.size() - 1 >= j)
                {
                    if (((gijun_fish - v[j]) / 5) != 0)
                    {
                        if ((gijun_fish - v[j]) < 0)
                            d_board[i][j] += ((((gijun_fish - v[j]) * -1) / 5) * -1);
                        else
                            d_board[i][j] += ((gijun_fish - v[j]) / 5);
                    }
                    
                }
            }
 
            if (i != n)
            {
                auto& v = fishbowl[i + 1].arr;
                if (v.size() - 1 >= j)
                {
                    if (((gijun_fish - v[j]) / 5) != 0)
                    {
                        if ((gijun_fish - v[j]) < 0)
                            d_board[i][j] += ((((gijun_fish - v[j]) * -1) / 5) * -1);
                        else
                            d_board[i][j] += ((gijun_fish - v[j]) / 5);
                    }
                }
            }
        }
    }
 
    // 물고기 수를 바꾸자
    for (int i = start; i <= n; i++)
    {
        for (int j = 0; j < fishbowl[i].arr.size(); j++)
        {
                fishbowl[i].arr[j] -= d_board[i][j];
        }
    }
 
}
 
void bokgu()
{
    vector<vector<int>> tmp;
    int start = not_one;
 
    while (fishbowl[start].cnt != 0)
    {
        tmp.push_back(fishbowl[start].arr);
        start--;
    }
 
    for (int k = 0; k < tmp.size(); k++)
    {
        for (int i = tmp[k].size() - 1; i >= 0; i--)
        {
            fishbowl[not_one].arr.clear();
            fishbowl[not_one].arr.push_back(tmp[k][i]);
            fishbowl[not_one].cnt = 1;
            not_one--;
        }
    }
}
 
void junban()
{
    fishbowl[1].cnt--;
    int tmp = fishbowl[1].arr[0];
 
    fishbowl[2].cnt++;
    fishbowl[2].arr.push_back(tmp);
 
    not_one = 2;
    is_one = 3;
    // 2부터 출발
    while (true)
    {
        int kugi = 0;
        bool flag = false;
        while (fishbowl[not_one].cnt > 1)
        {
            vector<int> v;
            v = fishbowl[not_one].arr;
            kugi = v.size();
            if (fishbowl[not_one + kugi].cnt == 0)
            {
                flag = true;
                break;
            }
            fishbowl[not_one].cnt = 0;
            fishbowl[not_one].arr.clear();
 
            for (int i = 0; i < kugi; i++)
            {
                fishbowl[is_one + i].cnt++;
                fishbowl[is_one + i].arr.push_back(v[i]);
            }
 
            not_one--;
        }
        if (flag)
            break;
 
        is_one += kugi;
        not_one = is_one - 1;
    }
    move_fish();
    bokgu();
}
 
// 두 번만 한다
void huban()
{
    int hanbun = n / 2;
    vector<int> ichi;
    for (int i = n / 2; i >= 1; i--)
    {
        ichi.push_back(fishbowl[i].arr[0]);
        fishbowl[i].arr.clear();
        fishbowl[i].cnt = 0;
    }
 
    int ichi_start = 0;
    for (int i = n / 2 + 1; i <= n; i++)
    {
        fishbowl[i].arr.push_back(ichi[ichi_start]);
        fishbowl[i].cnt++;
        ichi_start++;
    }
 
    // 2회차
    int mou = hanbun / 2;
 
    vector<vector<int>> ni;
    for (int i = hanbun + mou; i >= hanbun + 1; i--)
    {
        ni.push_back(fishbowl[i].arr);
        fishbowl[i].arr.clear();
        fishbowl[i].cnt = 0;
    }
 
    int ni_start = hanbun + mou + 1;
    not_one = ni_start;
 
    for (int k = 0; k < ni.size(); k++)
    {
        for (int x = ni[k].size() - 1; x >= 0; x--)
        {
            fishbowl[ni_start].arr.push_back(ni[k][x]);
        }
        fishbowl[ni_start].cnt += ni[k].size();
        ni_start++;
    }
 
    move_fish();
    not_one = n;
    bokgu();
 
    memset(chk, 0, sizeof(chk));
    for (int i = 1; i <= n; i++)
    {
        chk[i] = fishbowl[i].arr[0];
    }
}
 
int main()
{
    cin >> n >> k;
    int ans = 1;
    init();
    while (true)
    {
        add();
        junban();
        huban();
        if (check())
        {
            cout << ans << '\n';
            break;
        }
        ans++;
    }
}