Boj 1201) Nmk

LIS, LDS 만들기

백준 1201

설명

나이브한 풀이

부분을 m 개로 나눠서 각 부분에는 감소만하게, 부분끼리의 최댓값은 증가하게 만듬.

예를들어

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

이렇게 됨.

불가능한 경우는 m, k 를 이용해 만들 수 있는 수열의 최대/최솟값을 통해 구함.

• 최솟값
  • 최솟값의 경우는 m + k - 1 임.
  • 왜냐하면 증가하는 구간 -> 감소하는 구간 혹은 그 역에서 숫자 하나는 공유되기 때문임.
• 최댓값
  • 최댓값의 경우 위의 부분들마다 숫자를 꽉꽉 채워넣는 경우가 됨.
  • 그래서 최댓값의 경우 m*k 가 됨.

증명

작성중

시간 복잡도

O(n)

코드

int main()
{
	fastio;

	int n, m, k;
	cin >> n >> m >> k;
	if (n < m + k - 1 || n > m * k ) {
		cout << -1;
		return 0;
	}
	vector<deque<int>> parts(m);
	int cur = 1;
	for (; cur <= k; cur++) parts[0].push_front(cur);
	if (m > 1)
	{
		int p_i = (n - k) / (m - 1);
		int left = (n - k) % (m - 1);
		for (int i = 1; i < m; i++)
		{
			for (int j = 0; j < p_i && cur <= n; j++, cur++)
				parts[i].push_front(cur);
			if (cur <= n && left > 0)
			{
				parts[i].push_front(cur++);
				left--;
			}
		}
	}
	for (auto& p : parts)
		for (auto& c : p)
			cout << c << ' ';
}