백준 1911번

흙길 보수하기

시간 제한 : 2 초 메모리 제한 : 128 MB

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

해설

이 문제는 웅덩이를 덮는데 필요한 최소한의 널빤지 수를 구하는 문제입니다. 주어진 웅덩이들의 위치와 크기, 그리고 널빤지의 길이를 사용하여 웅덩이를 덮을 때 필요한 최소한의 널빤지를 계산합니다.

문제 해결 방법은 다음과 같습니다:

1. 웅덩이 정렬: 먼저 웅덩이의 시작 위치에 따라 웅덩이를 정렬합니다. 시작 위치가 같은 경우에는 끝 위치에 따라 정렬합니다.
2. 널빤지 배치: 웅덩이를 차례대로 확인하면서 각 웅덩이에 널빤지를 배치합니다. 만약 현재의 웅덩이가 이전에 놓인 널빤지에 의해 이미 덮여 있으면 (이전 널빤지의 끝 위치가 현재 웅덩이의 끝 위치보다 크거나 같은 경우), 현재 웅덩이에 추가적인 널빤지를 놓을 필요가 없습니다. 그렇지 않은 경우에는 현재 웅덩이를 덮기 위해 필요한 널빤지의 개수를 계산하고, 해당 개수만큼 널빤지를 놓습니다.
3. 결과 출력: 모든 웅덩이를 확인한 후, 놓인 널빤지의 총 개수를 출력합니다. 다음과 같은 방법으로 웅덩이를 덮는데 필요한 최소한의 널빤지 수를 구할 수 있습니다.

#define _CRT_SECURE_NO_WARNINGS    
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef struct line {
	int s;
	int e;
} Line;

int compare(const void* a, const void* b) {
	Line num1 = *(Line*)a;
	Line num2 = *(Line*)b;
	if (num1.s > num2.s)
	{
		return 1;
	}
	else if (num1.s == num2.s)
	{
		if (num1.e > num2.e)
		{
			return 1;
		}
		else {
			return -1;
		}
	}
	return -1;
}

int main()
{
	int a, b;
	scanf("%d %lld", &a, &b);
	Line line[a];
	for (int i = 0; i < a; i++)
	{
		scanf("%d %d", &line[i].s, &line[i].e);
	}

	qsort(line, a, sizeof(Line), compare);

	int count = 0, block = 0;

	for (int i = 0; i < a; i++)
	{
		if (block >= line[i].e)
		{
			continue;
		}
		if (block < line[i].s)
		{
			block = line[i].s;
		}
		int cnt = (line[i].e - (block + 1)) / b + 1;
		count += cnt;
		block += b * cnt;
	}
	printf("%d", count);
}