[백준]Baekjoon1201(Greedy Algorithm)(최대 부분 증가 수열 & 최대 부분 감소 수열 함께 만족)

문제 링크 : https://www.acmicpc.net/problem/1201

비슷한 문제를 풀 때 활용할만한 부분이 있어서 개념부분으로 따로 뺀 문제이다.

먼저 어떤 경우에 문제의 조건에 맞게 최대 부분 증가 수열의 길이가 M이고

최대 부분 감소 수열의 길이가 K인 수열을 출력할 수 있는지 살펴보겠다.

일단 주어지는 수 N은 M+K-1 이상이어야 한다.

당연히 증가,감소 수열이 한번씩은 나와야 하기 때문에 M+K라는 수식이 나오는 것이며

1이 빠지는 이유는 두 수열이 숫자 하나를 공유하기 때문이다.

예를들어 위의 예시에서 2 1 4 까지 보면 증가, 감소 수열이 하나씩 나타나는데

이 수열이 1을 공유하고있음을 볼 수 있다.

다음으로 N은 M*K보다는 작거나 같아야 한다.

예를들어 만약 M이 3이고 K가 4라고 할 때 위의 조건에 맞게 숫자를 꽉꽉 채워보면

아래그림과 같다.

고로 만약 N보다 M*K가 크다면 무조건 최대 증가수열이나 감소수열이 더 늘어날것이다.

이 문제를 푸는 방식 또한 위의 그림과 연관이 있는데

조건을 만족시켜주기 위해 최대 증가수열인 M개의 그룹을 만들되 그룹의 최대 숫자는

최대 감소수열의 길이인 K를 넘지 못하게 하면 

조건을 만족하는 수열을 만들 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, M, K;
	cin >> N >> M >> K;

	bool b = true;

	int limit = 1;
	int count = N;
	if (N < M + K - 1 || N > M*K) {
		b = false;
		printf("-1");
	}
	if (b)
	{
		while (1) {
			M = M - 1;
			count = count - K;
			if (M == 0) {
				for (int i = N; i >=limit; i--) printf("%d ", i);
				break;
			}
			if (count / M == 0 || count <=0) {
				for (int i = limit + K - 1 - (M - count); i >= limit; i--)
					printf("%d ", i);
				for (int i = limit + K - (M - count); i <= N; i++)
					printf("%d ", i);
				break;
			}
			else {
				for (int i = limit + K - 1; i >= limit; i--) {
					printf("%d ", i);
				}
				limit = limit + K;
			}

		}
	}
	printf("\n");
}