백준 1201 NMK C++

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

1201번: NMK

 

비둘기집 원리 참고

https://ko.wikipedia.org/wiki/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC

비둘기집 원리 - 위키백과, 우리 모두의 백과사전

1. 수열이 안되는 조건 (N의 최소조건)

1) 예시로 안되는 조건인 4 4 2와 되는 조건인 4 4 1을 비교를 해보자

최대 숫자는 4개이고, 가장 긴 증가하는 부분 수열은 4이다. 그리고 가잔 긴 감소하는 부분 수열은 2

최대 숫자는 4개이고, 가장 긴 증가하는 부분 수열은 4이다. 그리고 가잔 긴 감소하는 부분 수열은 1

첫번째는 1,2,3,4 라는 조건밖에 없는데 여기서 감소하는 부분수열은 하나를 선택하는것밖에 없다.

하지만 아래조건은 4 4 1 은  1,2,3,4에 하나를 선택하는 것이 되서 성립이 된다.

이것을 식으로 나타내보면

n>=m+k-1이 성립되야지 수열이 된다.  (4>4+2-1, 4>4+1-1

즉 안되는 조건은 n< m+k-1 

 

2) 위 조건은 되지만 비둘기집 원리 (N의 최대조건)

이것을 문제에 대입해보자

 

7 4 3 와 7 2 3을 비교해보자

7 4 3

이 경우는 크기가 3인 내림차순수열이 4개가 있을 수 있다는 뜻이다. 4*3=12  어떤 경우가 되든 7이상을 전부 쓰고 있다.

 

7 2 3

이 경우는 크기가 3인 내림차순 수열이 2개가 있을 수 있다는 뜻이다. 2*3=6 즉 6개가 필요한데 1개가 혼자 남아돈다.

아래 풀이로 과정을 진행한다면 3이라는 그룹을 만들고 나머진 4이다(즉 그룹이 하나 생성됬다.)

4를 내림차순하면 1이 초과되고(남아돈다) 오름차순하면 이미 만든그룹1+4 즉 5가된다 2<5 즉 초과이다.

 

즉 안되는 조건은 n>m*k

 

 

 

2.풀이

 

1. 1~N까지 오름차순 배열을 만든다.

2. K만큼의 감소하는 부분부열을 자르고 자른부분까지 내림차순 정렬을한다. (1번그룹이 만들어졌다.)

3. 이후 나머지 그룹을 만들어주고, 내림차순정렬을 반복하면된다. (M-1 1번 그룹이 만들어졌기 때문에 1을 빼준다.)

 

코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k;
vector<int> v;

int main()
{
	cin >> n >> m >> k;
    
	if (m + k - 1 > n || n > m * k)
	{
		cout << "-1";
		return 0;
	}
	for (int i = 1; i <= n; ++i)
	{
		v.push_back(i);
	}
	//바꿀시작위치
	auto iter = v.begin();
	sort(iter, iter + k, greater<int>());

	
	iter += k;
	int remain = n - k;
    //아직 정렬할 숫자가 남았다면
	if (remain != 0)
	{
		int group = remain / (m - 1);
        //그룹을 나눈 나머지 구하기
		remain = remain % (m - 1);
		for (int i = 0; i < m - 1; ++i)
		{
        	//나머지분배
			if (remain > 0)
			{
				sort(iter, iter + group + 1, greater<int>());
				remain--;
				iter += group + 1;
			}
			else
			{
				sort(iter, iter + group, greater<int>());
				iter += group;
			}
		}

	}


	for (int i = 0; i < v.size(); ++i)
	{
		cout << v[i] << ' ';
	}

}