백준 - NMK (1201)

6시간...

솔직히 풀다가 진짜 열도 받고 풀이 보고 싶은 욕망이 초단위로 들긴 했는데 그래도 참고 하니까 풀리긴 하네요.

문제

1201번: NMK

N: 1부터 N까지 들어있는 수열

M: 가장 긴 증가하는 부분 수열의 길이

K: 가장 긴 감소하는 부분 수열의 길이

이 세가지 조건에 충촉되는 수열을 구하는 문제 입니다.

접근

주어진 조건에 수열을 만드는 공식을 세우는 구성적 접근과 할 수 있는 데 까지 조건에 맞는 수열을 만들어 내야 하는 그리디 알고리즘 의 조합을 이루는 문제 입니다. 따라서 이 문제를 풀기 위해 저는 아래와 같이 접근을 시도했습니다.

최대한 수열을 만들도록 노력해야 하기 때문에, N,M,K이 세 값으로 수열이 될 수 있는 최소한의 조건식을 구한다.
수열이 길이 N 따라 주어진 M,K에 대한 부분 수열을 만들 수 있는 지에 대한 가능성이 판가름이 되며, M,K에 대한 N의 최소/최대 조건식을 구했다는 것은 수열을 만드는 공식을 유도하는 것과 같다.

1. 수열을 만들 수 있는 N,M,K에 대한 조건식 유도

1.1 N의 최솟값

M,K로 만들수 있는 가장 짧은 수열의 길이는 N을 중심으로 두고 왼쪽에는 증가 수열, 오른쪽에는 감소 수열을 배치하는 방법 입니다.

왼쪽은 [1, 2,  ..,  M-1]으로 M-1개, 중앙에 N으로 1개, 그리고 오른쪽에는 [N-1, N-2,  .. N-K+1]으로 K-1개, 따라서  N이 M+K-1보다 작으면 해당 조건에 맞는 수열을 만들 수가 없습니다.

1.2.. N의 최댓값

N의 최솟값을 구하는 건 쉬웠지만, N의 최댓값을 구하는 건 상당히 어려운 일이었습니다. 왜냐하면 N의 최댓값을 구하는 과정이 결국 수열을 만드는 공식으로 이어지기 때문입니다.  어떻게 해야 할 지 고민한 끝에, 아래와 같이 감소 수열을 증가 수열의 갯수 만큼 나열하기로 합니다. 단 각 감소 수열의 범위는 겹치지 않게 나열합니다.

수열 그래프, 초록색이 수열의 요소들, 파란색이 감소하는 수열, 빨간색이 증가하는 수열이다.

이렇게 되면 N의 최댓값이 될 수 있는 경우는 가장 긴 감소하는 수열이 M개 있는 것과 같으며 이에 대한 공식은 아래와 같습니다.

따라서 N에 대한 범위를 정리하면

2. 수열 만들기

N의 최댓값에서 보았듯이, 가장 긴 감소 수열을 M개 만큼 나열하면 그게 N의 최댓값이 된다고 했습니다. 그렇다면 N이 최대값이 아니라면 어떻게 해야 할까요?

정답은 M개의 감소 수열을 상황에 맞게 조절을 하면 됩니다. 단 각 감소 수열의 길이 중 최소 하나 이상은 K가 되어야 조건에 맞게 됩니다.

예를 들어 {N=10, M=4, K=3}라는 조건 있다고 가정합시다. 가장 긴 감소 수열을 4개를 만든다고 하면 총 12개가 되므로 첫 번 째 감소 수열을 제외한 나머지 감소 수열의 요소 갯수를 일부 제거합니다.

즉, [3,2,1] - [6,5,4] - [7,8,9] - [12,11,10] 은 총 12개가 되므로 N의 갯수 10개에 맞게 중간 두 개의 감소 수열에 요소를 하나 씩 제거하면 [3,2,1] - [5,4] - [7,6] - [10,9,8] 이 됨으로써 갯수가 맞게 됩니다.

코드보기(C)

#include <stdio.h>
#include <math.h>

int solution(int n, int m, int k)
{
	int i;
	// 수열을 만들 수 있는 지 검토
	if(m+k-1>n) return -1;
	if(n>m*k) return -1;
	
	// 먼저 가장 긴 감소 수열을 만든다.
	for(i=k;i>=1;i--) printf("%d ", i);
	if(m>1)
	{
		// 가장 긴 증가 수열의 길이가 1 이상이면
		// 반복문을 돌면서 M-1개의 길이가 K-1 이하의 감소 수열을 만든다.
		int i = k;
		int j = (m-1);
		while(j>0)
		{
			int a;
			int p = (int)(n-i)/j;
			i += p;
			for(a=i;a>i-p;a--) printf("%d ", a);
			j--;
		}
	}
	return 0;
}

int main(void)
{
	int n,m,k;
	scanf("%d %d %d", &n, &m, &k);
	int res = solution(n,m,k);
	if(res == -1)	printf("-1\n");
	return 0;
}

(참고) Erdős–Szekeres 이론

The Erdős–Szekeres theorem

Theorem [Erdős-Szekeres 1935]
For given positive natural numbers s,r, any sequence of distinct real numbers whose length is at least N = s r + 1 contains a monotonically increasing subsequence of length s + 1 or a monotonically decreasing subsequence of length r + 1 (or both)

모든 수열에는 항상 길이가 (s+1)인 증가(감소) 수열과 길이가 (r+1)인 감소(증가) 수열이 존재한다는 논문이며 s,r에 대한 N의 최솟값에 대한 이론으로 보입니다. 해당 링크에는 증명도 있으니 관심있는 분들은 해당 링크를 참고하시면 되겠습니다.