흔한 수열 문제


작성일 : 2017-01-22 01:55:32
조회수 : 631



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


이 문제는 일단 풀고난 다음 굉장한 보람을 느꼈습니다. 그 이유는 아래 사진을 보면 됩니다.



알고리즘을 본격적으로 공부한 것은 2015년 이고, 군대 가기 전에 깔짝 대던 것은 2012년 부터였는데, 이 때는 이걸 풀면서 정말 나는 평생 이런 문제를 못 풀거라고 생각했습니다. 그리고 우연한 기회에 이걸 틀렸던 것을 확인하여 이번에 해결하였습니다.


이 문제는 1 x y z 또는 2 x y z 의 형태로 인풋이 주어지는데, 1이 올 경우 x~y번째의 수 중 가장 큰 것은 z이며, 2가 오면 그 반대가 됩니다. 그러므로 그 조건과 반대가 되는 수와 장소는 모두 숫자를 올 수 없다고 체크를 합니다. 예를 들어 1~4로 이루어진 수열이 있을 때, 1 1 3 2 가 왔다고 하면 1~3번째 위치에는 3,4과 올 수 없으며, 4번째 장소에는 2가 올수 없으므로 이를 올 수 없다고 처리합니다.


그 다음, 올 수 있는 부분을 모두 그래프로 연결해 줍니다. 이 문제는 한 자리에 숫자가 1개씩 들어가면 되므로 유량이 1인 네트워크 플로우 문제가 되며, 이를 최대 이분 매칭으로 변형하여 풀 수 있습니다. 이 때, 매칭이 되는 최댓값이 항상 n과 같아야 모든 자리에 수열의 원소가 들어간 것이므로, 들어가지 못했다면 -1, 들어갔다면 저장한 숫자를 출력해주면 됩니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool a[201][201], visited[201];
int match[201], bm[201];
vector<vector<int> > v;
bool bpm(int n)
{
    if (visited[n]) return false;
    visited[n] = true;

    for (auto it : v[n])
    {
        if (match[it] == -1 || bpm(match[it]))
        {
            match[it] = n;
            bm[n] = it;
            return true;
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    

    cin >> n >> m;
    v.resize(n + 1);

    //a : [place][no]
    for (int i = 0; i < m; i++)
    {
        int c, x, y, z;

        cin >> c >> x >> y >> z;
        if (c == 1)
        {
            for (int j = x; j <= y; j++)
                for (int k = z + 1; k <= n; k++)
                    a[j][k] = true;
        }
        else
        {
            for (int j = x; j <= y; j++)
                for (int k = 1; k < z; k++)
                    a[j][k] = true;

        }
        for (int j = 1; j < x; j++) a[j][z] = true;
        for (int j = y + 1; j <= n; j++) a[j][z] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!a[i][j])
                v[i].push_back(j);

    fill(match, match + n + 1, -1);
    int cmp = 0;
    for (int i = 1; i <= n; i++)
    {
        fill(visited, visited + n + 1, false);
        if (bpm(i)) cmp++;
    }
    if (cmp != n) cout << "-1\n";
    else
        for (int i = 1; i <= n; i++) cout << bm[i] << " ";
}

흔한 수열 문제 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글