Problem 1201

NMK

문제

1부터 N까지의 수를 한 번씩 이용해서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 출력한다.

입력

첫째 줄에 N M K가 주어진다. N은 500보다 작거나 같은 자연수, M과 K는 N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 정답이 없다면-1을 출력한다

문제 링크

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

예제 입력 1

4 2 2

예제 출력 1

2 1 4 3

solve

적어도 m개는 증가수열에 포함되어야 하고 적어도 k개는 감소수열에 포함되어야 한다. 두 수열은 최대 1개의 정수를 공유 가능
- [ex) m = 3, k = 2 -> 1 2 4 3 과 같이 3개가 증가하고 이어서 4를 공유하여 2개가 감소하는 경우 최소 길이]
- 따라서 n >= m + k -1 를 만족해야 한다.
예를 들어, 1 2 3 4 5 6 7 8 9를 4개씩 묶는다고 생각해보자.
- (1 2 3 4)(5 6 7 8)(9) 와 같이 묶고, 각 구간을 뒤집는다.
- (4 3 2 1)(8 7 6 5)(9) 가 될 것이다. 이 경우, 각 구간 내에서는 증가하는 부분이 없으므로 구간의 개수가 증가하는 최대 부분수열의 개수가 된다. 또한 구간의 최대 길이가 감소한는 부분 수열의 최대 길이가 될 것이다.
감소하는 부분 수열의 길이를 k가 되도록 하기 위해 오름차순으로 정렬된 k개의 수에 대해 앞에서부터 한번은 최대 k개가 되도록 묶어 뒤집어 준다.
또한 m개의 증가 수열을 만들어 주기 위해 뒤집힌 묶음의 개수가 m개가 되어야 한다.
즉, m개의 구간을 묶을 때, 적어도 한 번은 k개가 되도록 수를 묶어 모든 구간을 뒤집어 주면 정답을 구할 수 있다.
이때, n이 m * k보다 커지게 된다면, m개의 구간을 k개씩 묶고 나서도 1개 이상의 수가 남기 때문에 이 경우 정답을 구할 수 없다.

코드 설명

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<climits>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, k;
	cin >> n >> m >> k;

	if (n < m + k - 1 || n > m * k) // 불가능한 범위 처리
	{
		cout << -1 << '\n';
		return 0;
	}

	vector<int> a(n);
	for (int i = 0; i < n; i++)
		a[i] = i + 1;
	vector<int> s; // 구간을 나눌 지점을 저장할 벡터
	s.push_back(0); // 첫 구간의 시작
	s.push_back(k); // 첫 구간의 끝
	n -= k; // 남은 수의 개수
	m--; // 남은 구간 수

	int q = m == 0 ? 1 : n / m; // 남은 구간이 없다면 1
	int r = m == 0 ? 0 : n % m;

	for (int i = 0; i < m; i++) // 남은 구간 수 만큼
	{ // r(나머지)가 0이 될때까지 각 구간에 1씩 추가한다.
		s.push_back(s.back() + q + (r > 0 ? 1 : 0));  // 마지막 원소에 나눌 구간 크기만큼 더하여 추가
		if (r > 0) r--; // 나머지 감소
	}

	for (int i = 0; i < s.size() - 1; i++)
		reverse(a.begin() + s[i], a.begin() + s[i + 1]); // s에 저장된 구간으로 나누어 뒤집음

	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << '\n';
}

백준 1201번 NMK

Baekjoon algorithm

Problem 1201

NMK

문제

입력

출력

문제 링크

예제 입력 1

예제 출력 1

solve

코드 설명

FEATURED TAGS

FRIENDS