[c++] 백준 #1201 NMK

재미있는 그리디 문제이다. 2년 전에 손도 못대던 문제를 풀었더니 기분이 좋다.

 

www.acmicpc.net/problem/1201

<풀이>

문제 내용은 1부터 N까지의 수를 한 번씩 이용해서 가장 긴 증가하는 부분 수열의 길이가 M이고, 가장 긴 감소하는 부분 수열의 길이가 K인 수열을 출력한다는 것이다.

 

숫자를 배열하면서 규칙을 찾아보면, 숫자를 오름차순 해둔 상태에서 M개의 그룹을 만들고, 각각의 그룹을 내림차순하면, 가장 긴 증가하는 부분 수열의 길이를 M으로 만들 수 있다. 그러면, 각각의 그룹 내에 감소하는 부분 수열이 존재하기 때문에, 그룹에 들어가는 원소의 수 중 최댓값이 K가 되게 된다.

따라서, 이 문제는 M개의 그룹에 최대 K개의 원소를 배치하는 문제로 바뀌게 된다. (무언가 굉장히 많이 본 형태!)

 

M개의 그룹에 최대 K개의 원소를 배치할 수 있다면, 전체 시퀀스 길이 N은 M*K를 넘을 수 없다. (비둘기집의 원리라고 생각해도 되는데 자명하다)

또한, 증가하는 부분 수열과 감소하는 부분 수열의 길이는 최소 숫자 한개만큼은 공유하기 때문에 M+K-1 <= N이 성립한다. (간단하게 1,2,3,4,5 시퀀스가 있을 때 M=5, K=1이 되는 것을 생각해보면 이 또한 자명하다)

 

그래서 이 두 가지 경우를 예외 컨디션으로 넣어주면 끝이다.

 

그냥 여기까지만 생각하고 맨 마지막 그룹에 K개의 원소를 넣어주고 나머지 그룹에 (N-K) / (m-1)개의 원소를 넣어주고 m-1번째 그룹에 나머지를 더한만큼 원소를 넣어주는 식으로 문제를 푸니 틀렸습니다가 떴다. 그러다 m=1일 때 예외 처리 안해준 것을 발견하고 수정하고, 다시 곰곰이 생각해보니, 다음의 반례가 있었다.

21 6 4

내 알고리즘대로라면 원소를 1 2 3 / 4 5 6 / 7 8 9 / 10 11 12 / 13 14 15 16 17 / 18 19 20 21 이렇게 나누게 되어서 중간에 K개보다 많은 수의 원소를 가진 그룹이 발생하게 된다.

즉, 위의 풀이 방식으로는 각 그룹에 최대 K개의 원소가 들어가는 조건이 성립하지 못하게 된다.

 

따라서, 풀이 방법을 다음과 같이 바꿔주었다. 맨 마지막 그룹에는 K개가 들어가게 그대로 유지하고, 나머지 그룹에는 N<=M*K라는 조건 때문에 나머지를 제외하면, 각 그룹에 들어가는 원소의 수(n_elem)는 최대 K개를 만족한다. 따라서 나머지의 수를 미리 계산해둔 후, n_elem이 K보다 작으면 n_elem + 1개의 원소를 그룹에 넣어주는 식으로 진행하였다. 그렇게 하면, 각 그룹에는 최대 K개의 원소가 들어가고, 나머지는 그룹의 개수보다는 항상 적을 수 밖에 없기 때문에 식의 조건을 성립하는 상태로 원소를 배치할 수 있다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back


int seq[501];
int N, M, K;

bool compare(int i, int j){
    return j < i;
}

int main(){
    cin >> N >> M >> K;
    int lower_bound = M+K-1;
    int upper_bound = M*K;
    if (lower_bound <= N && N <= upper_bound){
        // initialize : sorted
        for (int i=0; i<N;i++){
            seq[i] = i+1;
        }
        int final_group_idx = N-K;
        sort(seq+final_group_idx, seq+N, compare);
        
        int n_elem;
        int remainder;
        if (M == 1){
            n_elem = 0;
            remainder = 0;
        }
        else {
            n_elem = (N-K) / (M-1);
            remainder = (N-K) % (M-1);
        }
        
        int start = 0;
        int end = 0;
        for(int i=1; i<M;i++){
            if (n_elem < K && remainder){
                end += n_elem + 1;
                remainder--;
            }
            else {
                end += n_elem;
            }
            sort(seq+start, seq+end, compare);
            start = end;
        }

        for (int i=0;i<N;i++){
            cout << seq[i] << " ";
        }
        cout << '\n';
    }
    else {
        cout << "-1\n";
    }





    return 0;
}