[백준] 1449번: 수리공 항승

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

1449번: 수리공 항승

 

난이도: solved.ac 실버 3

 

 

물이 새는 위치를 수직선 위에 표시한다고 해보자

 

(테이프의 길이) - 1보다 물이 새는 위치의 간격이 작으면

 

한 테이프로 이어붙일 수 있다

 

(양 끝에 0.5 간격은 남겨야하기 때문)

 

일단 위치를 크기순으로 나타내기 위해

 

qsort를 이용해 정렬시켜주었다

 

그리고 맨 첫번째 구멍 위치부터 시작해

 

기준이 되는 위치부터 다음 구멍의 위치까지의 길이를 파악해서 L보다 작은지 비교하고

 

L보다 작으면 한 테이프로 붙일 수 있다는 것을 의미하므로

 

구멍 사이의 간격이 L보다 커질 때까지 비교하고

 

L보다 커지면 테이프의 개수를 늘려가는 방식으로 풀었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int compare(int* a, int* b) {
	return *a - *b;
}

int main() {
	int N, L;
	scanf("%d %d", &N, &L);
	int* arr = (int*)malloc(sizeof(int) * N);
	int i, j;
	for (i = 0; i < N; i++)
		scanf("%d", &arr[i]);
	qsort(arr, N, sizeof(int), compare);	// 정렬시켜줌

	int cnt = 0;	// 사용할 테이프의 갯수
	int start = arr[0];	// start: 이어붙일 수 있는지 파악할 때 구멍의 맨 앞 위치
	for (i = 1; i < N; i++) {
		if (arr[i] - start < L)
			continue;
		
		else {
			cnt++;	// 옆의 것과 이어붙일 수 없으면 테이프를 새로 써야 함
			start = arr[i];	// 기준점 변경
		}
	}
	cnt++;
	printf("%d", cnt);
	free(arr);
	return 0;
}