03.02. 수리공 항승[Greedy Algorithm][백준 1449]

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

1449번: 수리공 항승

 

Algorithm classification : Greedy Algorithm, Sorting

 

03.02.1. Problem

Hang Seung is a repairman for a seriously poor quality water pipe company. Hang Seung went to repair the news that there was a water leak in the Sejun subway construction. The place where the water leaks from the pipe is strangely, only the distance from the farthest left to an integer number of water leaks. Hang Seung has an infinite number of tapes of length L. Hang Seung tries to block the water using a tape. Hang Seung always thinks that when blocking the water, it must be spaced at least 0.5 to the left and right of the location so that the water does not leak again. Write a program to find the minimum number of tapes required by Hang Seung, given the location of the leak and the length L of the tape he has. The tape cannot be cut, and it is possible to overlap the tape.

 

03.02.2. Input limit

The first line gives the number of leaks N and the length of the tape L. The second line gives the location of the leak. N and L are natural numbers less than or equal to 1,000, and the location of the leak is a natural number less than or equal to 1,000.

 

03.02.3. Output

In the first line, print the number of tapes that need to be multiplied.

 

03.02.4. Solution

캠핑과 동일한 방식입니다. Greedy choice property와 optimal substructure에 해당하는지 고민해보시면 좋을 것 같습니다.

	sort(data, data+n);
	int start;
	
	for(i = 0; i < n;){
		start = data[i];
		c++;
		while(data[i] - start <= l-1) i++;
	}
	printf("%d", c);