[그리디 알고리즘] NMK

예제 입력 1

4 2 2

예제 출력 1

2 1 4 3

 

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

1201번: NMK

- 풀이

N = 10, M = 3, K = 4라고 가정하자. 1부터 N까지를 오름차순으로 적는다. (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

 

K(최대 부분 감소 수열의 길이)만큼 그룹을 나눈다. ( [1 2 3 4] 5, 6, 7, 8, 9, 10)

 

모두 합하여 M개의 그룹이 되도록 나머지 그룹되지 않은 수를 그룹을 짓는다.

( [1 2 3 4] [5 6 7] [8, 9, 10] )

 

각 그룹별로 뒤집으면 문제 조건에 맞는 수열이 만들어진다.

( [4 3 2 1] [7 6 5] [10 9 8] )

 

* 최대 증가 부분 수열 : 각 그룹에서 숫자 하나씩 꺼내면 나옴.

* 최대 감소 부분 수열 : 맨 앞의 그룹이 최대 감소 부분 수열임.

 

- 가능한 경우 #1 : 길이가 N일 때 최대 부분 증가 수열의 길이가 M이고 최대 부분 감소 수열의 길이가 K이면, 최소한 1개의 원소만 공유될 수 있기 때문에, 가능하려면 적어도 N은 M+K-1보다 크거나 같아야 한다. (M+K-1 <= N)

- 가능한 경우 #2 : N은 MK를 넘을 수 없다. (N <= MK) 왜냐하면, 길이가 K인 1개 그룹을 빼고 나머지 각 그룹의 크기는 K와 같거나 K보다 작아야 하기 때문이다. (최악의 경우 = 모든 각 그룹의 크기가 K, 그 그룹이 M개)

 

#include <stdio.h>

constexpr int MAX_SIZE = 501;

int N, M, K;

int arr[MAX_SIZE];

void reverse(int start, int end)
{
	while (start < end)
	{
		int temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;

		start++;
		end--;
	}
}

class vector
{
public:
	int data[MAX_SIZE];
	int size;

	vector() { size = 0; }

	void push(int item)
	{
		data[size] = item;
		size++;
	}

	int top()
	{
		return data[size - 1];
	}
};

int main(void)
{
	scanf("%d %d %d", &N, &M, &K);

	int copyN = N;

	for (register int i = 0; i < N; i++)
		arr[i] = i + 1;

	if (M + K - 1 <= N && N <= M * K)
	{
		vector splitPosition;

		splitPosition.push(0);
		splitPosition.push(K);

		N -= K;
		M -= 1;

		int splitGroupSize = M == 0 ? 1 : N / M; //  M개의 그룹
		int splitGroupSizeMod = M == 0 ? 0 : N % M; // 나머지는 각각 M개의 그룹에 1개씩 배분

		for (int i = 0; i < M; i++)
		{
			splitPosition.push(splitPosition.top() + splitGroupSize + (splitGroupSizeMod > 0 ? 1 : 0));

			if (splitGroupSizeMod > 0) splitGroupSizeMod--;
		}

		for (int i = 0; i < splitPosition.size - 1; i++)
		{
			reverse(splitPosition.data[i], splitPosition.data[i+1] - 1);
		}

		for (int i = 0; i < copyN; i++)
			printf("%d ", arr[i]);

		printf("\n");
	}
	else
	{
		printf("-1\n");
	}

	return 0;
}