[백준] 1201번 NMK

[풀이]

이 문제는 N개의 수를 M개의 덩이로 나누어서 그를 역순으로 하는 문제 입니다.

우선,

M + K - 1 <= N <= M * K

이 조건에 해당할 때만 정답이 나올 수 있는데요,

먼저 M + K -1 <= N인 경우는 증가와 감소가 최대 정수 하나를 반드시 포함하기에 어떻게 보면 당연한 조건 입니다.

위 그림의 경우 M + K - 1 = N 이고 M이나 K구간의 길이가 M,K보다 작을 수 있으니

(321 654 의 경우는 M은 2인데 최대정수 전 까지의 길이는 3입니다.) N이 이보다는 크겠죠?

그리고 M * K 의 경우는 비둘기집 원리를 통해 증명할 수 있습니다.

(비둘기집의 원리 - mathsolver님의 글을 참조. https://steemit.com/kr/@mathsolver/2-1-1)

간단하게 이 문제의 경우를 보면, N개의 수를 M개의 덩이로 나누어서 풀어야 하는데, 그렇게 되면

N = M * N/M + r(나머지) 이렇게 표현할 수 있습니다.

그리고 나머지는 0보다 크거나 같겠죠?

그러면 N/M 을 K로 대입해보면

N/M <= K (r이 0일 경우는 N/M = K 겠지만 클 경우는 N/M이 K보다 작아야 식이 성립합니다.)

-> N <= MK 를 도출해낼 수 있습니다.

따라서,

1. M + K - 1 <= N <= M * K

2. N개의 수를 M개씩 나누어 풀이

아래는 위 사항들을 적용하여 풀이한 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool desc(int a, int b) {
    return a > b;
}
int find(vector<int> arr, int inc, int dec) {
    int len = arr.size();
    if (inc - 1 > len - dec || len-dec < 0) {
        return 0;
    }
    vector<int> newArr;
    for (auto x : arr) newArr.push_back(x);

    sort(newArr.begin() + (len - dec), newArr.end(), desc);


    if (inc - 1 == len - dec) {
        for (auto x : newArr) cout << x << ' ';
        return 1;
    }
    else {
        vector<int> nextArr;
        for (int i = 0; i < len - dec; i++) nextArr.push_back(newArr[i]);
        int result = 0;
        for (int i = 2; i <= dec; i++) {
            result = find(nextArr, inc - 1, i);
            if (result) break;
        }
        if (result) {
            for (int i = len - dec; i < len; i++) cout << newArr[i] << ' ';
            return 1;
        }
        else return 0;
    }
}
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> arr;
    for (int i = 1; i <= n; i++) {
        arr.push_back(i);
    }
    if (!find(arr, m, k)) cout << -1;
    return 0;
}