백준 알고리즘 문제 풀이 c/c++ -1449-

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

• 입력값들을 먼저 오름차순 정렬
• 첫 번째 원소 부터 막을 수 있는 곳의 최대값 구한다
• 반복문을 돌면서 위 값보다 큰 곳이 나오면 그 값을 기준으로 다시 막을 수 있는 최대값을 구하고 사용 테이프 개수를 하나 증가시킨다

#include <stdio.h>
#include <algorithm>

using namespace std;


int n; // 물 새는곳 개수
int L; // 테이프 길이

int arr[1010]; // 새는 위치 담을 배열

int Count = 0; // 필요한 테이프 개수

int main() {

	scanf("%d %d", &n, &L);

	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	sort(arr, arr + n);  // 오름차순 정렬

	int possible = arr[0] + L - 1;
	Count = 1;

	for (int i = 0; i < n; i++) {
		
		if (arr[i] > possible) {
			Count++;
			possible = arr[i] + L - 1;
		}
	}

	printf("%d\n", Count);


	return 0;
}