[백준 27986번] 평범한 구성적 문제

 

27986번: 평범한 구성적 문제

---

문제가 수학적인 표현이 많이 쓰여, 다소 이해하기 어렵다고 생각한다.

문제 설명

문제에서 요구하는 것은 배열 $X$를 구하는 것이며, 배열 $X$는 $1$부터 $K$이하의 수로 구성되어 있다.

문제의 입력으로 주어지는 것들은 조건이며, 조건들을 만족하면서 $K$가 최대가 되게 하는 배열 $X$를 구하는 문제이다.

$K$의 최대값은 하나지만, 이때 배열 $X$는 여러 가지 경우가 나올 수 있다.

(편의상 $K'$을 $K$의 최대값이라 정의하겠다)

 

문제 접근

문제에서 주어지는 입력 중에서 $R_i - L_i + 1$ (구간의 길이)가 $L$이라고 하면,

($L$안에 들어갈 수 있는 원소의 종류의 최대는 $L$이므로) $K'$은 $L$이하여야 한다.

따라서, 모든 $(L_i, R_i)$에 대해서 $R_i - L_i + 1$ 값 중에서 최소값이 $K'$이 된다는 것은 직감적으로 알 수 있을 것이다.

 

결론적으로, $K'$을 구한 후에 모든 $(L_i, R_i)$에 대해 조건에 맞게끔 적절히 배열 $X$를 구성하면 된다.

 

더 좋은 방법

$K'$이 정해지면, $(L_i, R_i)$의 값에 상관없이 항상 답을 만족하는 배열 $X$를 만들 수 있다.

즉, $K'$이 정해지면, $(L_i, R_i)$의 최악의 경우에도 답을 만족하는 $X$가 항상 존재한다는 것이다.

 

예를 들어 $N=7$, $K'=3$이라고 하면, 이때 최악의 $(L_i, R_i)$ 값은 $(1, 3)$, $(2, 4)$, $(3, 5)$, $(4, 6)$, $(5, 7)$ 이다.

이때, $1231231$ 와 같이 배열 $X$를 구성하면 항상 답이 된다.

(직접 해보면, 조건을 만족한다는 것을 알 수 있을 것이다.)

(항상 조건을 만족하는 배열 $X$가 존재하는 이유는 문제의 조건이 연속된 구간 단위로 주어지기 때문이라고 생각하면 된다.)

 

똑같이, $K'=5$라면 $N$의 길이에만 맞춰서 $1234512345123451234512345...$ 이런식으로 배열$X$를 구성하면 된다.

 

최악의 경우($K'$길이의 모든 $(L_i, R_i)$쌍이 있는 경우)에도 위의 방법대로 배열 $X$를 구성하면 조건을 만족했다.

따라서, 입력에 대해 $K'$( = $R_i - L_i + 1$의 최소값)을 구하고 $1234...K'1234...K'....$ 와 같이 배열 $X$를 구성하면 된다.

 

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M; cin >> N >> M;
	int k = INT_MAX;
	while (M--) {
	int a, b; cin >> a >> b;
	k = min(k, b-a+1);
	}
	for (int i=1; i<=N; i++) {
	cout << (i % k == 0 ? k : i % k) << ' ';
	}
	return 0;
	}

view raw 27986.cpp hosted with ❤ by GitHub