[BOJ 1201] NMK

문제

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

1201번: NMK

 

---

알고리즘

• 그리디
• 구성적

---

풀이

LIS와 LDS의 공통 원소는 무조건 1개이므로 바이토닉 수열 형태로 문제를 해결할 수 있습니다.

먼저 \(N - M + 1\)부터 \(N\)까지의 수로 앞을 채우고, \(K - 1\)부터 \(1\)까지의 수로 그다음을 채웁니다. LDS의 첫번째 원소는 LIS의 마지막 원소이므로 \(K - 1\)개만 채우면 됩니다. 나머지 수들은 이 원리로 채워 나가면 되는데, \(N\)과 \(1\)을 채우지 않은 수들 중 최대값과 최소값으로 바꾸면서 범위를 줄여나갑니다. 그리고, \(M\)과 \(K\)는 바로전 LDS와 LIS에서 현 LIS와 LDS의 원소를 1개씩 받을 수 있기 때문에 각각 \(1\)을 빼줍니다.

 

5번째 예제인 \(N=13, M=5, K=4\)로 예를 들어보겠습니다.

우리는 \(13\)개의 수를 채워야 합니다.

$$\cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot$$

먼저, 상위 \(M(5)\)개의 수를 채워넣습니다.

$$9\ 10\ 11\ 12\ 13\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot$$

\(K\)에 대해선 채워진 수들 중 하나가 LDS의 첫 원소가 될 수 있으므로 \(1\)을 뺍니다. \(\ (K=3)\)

그다음 하위 \(K(3)\)개의 수를 채워넣습니다.

$$9\ 10\ 11\ 12\ 13\ 3\ 2\ 1\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot$$

이제 채워지지 않은 수들 중 최대값은 \(8\), 최소값은 \(4\)가 됩니다.

다음으로, \(M\)에 대해선 \(3, 2, 1\)중 하나가 LIS의 첫 원소가 될 수 있으므로, \(1\)을 뺍니다. \(\ (M=4)\)

채워지지 않은 수들 중 상위 \(M(4)\)개의 수를 채워넣습니다.

$$9\ 10\ 11\ 12\ 13\ 3\ 2\ 1\ 5\ 6\ 7\ 8\ \cdot$$

\(K\)에 대해선 전과 같이 \(1\)을 빼줍니다. \(\ (K=2)\)

채워지지 않은 수들 중 하위 \(K(2)\)개의 수를 채워넣습니다. 채워지지 않은 수는 \(4\) 하나이므로 \(4\)를 채워넣으면 수열이 완성됩니다.

$$9\ 10\ 11\ 12\ 13\ 3\ 2\ 1\ 5\ 6\ 7\ 8\ 4$$

 

가능한지 불가능한지는 \(N \leq 500\)이므로 LIS와 LDS를 구하는 기본적인 방법을 사용해 입력받은 \(M, K\)와 비교해 알 수 있습니다.

 

시간복잡도: \(O(N^2)\)

 

---

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K; cin >> N >> M >> K;
    int ans[500], x = M, y = K;

    int l = N, r = 1, idx = 0;
    while (idx < N && l >= r) {
        for (int i = 1; i <= M && idx < N; ++i, ++idx)
            ans[idx] = l - M + i;
        K--;
        K = min(K, l - M + 1 - r);
        if (l <= r) break;
        for (int i = 1; i <= K && idx < N; ++i, ++idx)
            ans[idx] = r + K - i;
        l -= M, r += K, M--;
        M = min(M, l - r + 1);
    }

    int lis[500], lds[500];
    fill(lis, lis + N, 1), fill(lds, lds + N, 1);
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (ans[j] < ans[i]) lis[i] = max(lis[i], lis[j] + 1);
            else lds[i] = max(lds[i], lds[j] + 1);
        }
    }

    if (*max_element(lis, lis + N) != x || *max_element(lds, lds + N) != y) {
        cout << "-1\n";
        return 0;
    }

    for (int i = 0; i < N; ++i)
        cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}