백준 27986 : 평범한 구성적 문제

문제 설명

---

M개의 범위가 주어졌을 때 해당 범위에 1~k까지의 수가 모드 들어가는 N개의 배열을 만들려고 한다. k의 값이 최대가 되는 배열을 출력하는 문제이다.

---

 

해당 문제에서 최대 k의 값은 주어진 범위의 크기들중 최솟값과 같다. 모든 범위에 1~k의 값이 들어가야 하기 때문에 k의 최댓값은 주어진 모든 범위중 가장작은 범위의 크기를 넘을 수 없기 때문이다. 따라서 우리는 이에 따라 최대 k의 값을 정할 수 있다. 이제 k값을 가지고, 주어진 조건을 만족하는 N개의 수열을 만들면 된다. 이때, 모든 구간은 "연속" 함으로 1~N까지 1~k를 반복해 넣어주기만 하면 된다.

예를 들어 N = 10, k = 3이라면 {1, 2, 3, 1 ,2 , 3, 1, 2, 3, 1}과 같은 식으로 구성해주면 된다는 뜻이다.

---

소스 코드

#include <stdio.h>

int n, m, k = 2e9;

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (k > y - x + 1) k = y - x + 1;
	}
	int num = 1;
	for (i = 0; i < n; i++) {
		printf("%d ", num++);
		if (num > k) num = 1;
	}
	return 0;
}

 

 K를 구하는 방법은 쉽게 알았지만, 해당 k를 이용해 배열을 구성하는데 애를 먹었다. 처음에는 모든 범위를 차례로 탐색해가며 채우는 등 삽질을 많이 했던 문제.