백준1449 - 수리공 항승

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

1449번: 수리공 항승

그리디의 기초인 문제라고 하는데 나는 되게 오래걸렸다.

그리디는 아이디어 문제인 경우가 많다.

여기서는 수직선의 원리를 이용하여 풀었다.

구멍사이의 간격은 테이프의 길이 - 1을 한 것으로 비교한다. 이유는 테이프의 시작과 끝을 0.5로 준다.

구멍사이의 간격보다 테이프의 길이가 짧으면 테이프의 갯수를 한 개씩 증가시킨다.

테이프를 붙이는 곳(min)은 구멍사이의 간격보다 테이프의 길이가 짧아진 순간의 구멍을 테이프를 붙이는 곳으로 설정한다. 

 

ex.1)

구멍은 세 곳 , 테이프의 길이는 2, 구멍의 위치는 4, 5, 9

5 - 4 = 1 -> 테이프 붙이는 곳의 위치를 갱신하지 않는다.    테이프 갯수 1

9 - 4 = 5 -> 테이프 붙이는 곳이 위치를 갱신한다.              테이프 갯수 2

총 테이프 갯수 2

 

ex.2)

구멍은 네 곳, 테이프의 길이는 3, 구멍의 위치는 1, 3, 5, 7

3 - 1 = 2 -> 테이프를 붙이는 곳의 위치를 갱신하지 않는다.   테이프 갯수 1

5 - 1 = 4 -> 테이프를 붙이는 곳의 위치를 갱신한다.             테이프 갯수 2

7 - 5 = 2 -> 테이프를 붙이는 곳의 위치를 갱신하지 않는다.    테이프 갯수 2

9 - 5 = 4 -> 테이프를 붙이는 곳의 위치를 갱신한다.             테이프 갯수 3

총 테이프 갯수 3

 

#include <iostream>
#include <string.h> //memset을 위해 선언
#include <algorithm>
using namespace std;

int main() {
	int mat[1001]; //최대 1000개를 입력한다.
	int N, L; //N은 구멍난 곳에 갯수, L은 테이프의 길이
	int min; //제일 왼쪽 값(테이프가 시작하는 지점)
	int cnt = 1; //


	memset(mat, 0, sizeof(mat)); //메모리공간을 0으로 초기화


	cin >> N >> L; 


	//구멍난 곳의 위치를 N개만큼 입력
	for (int i = 1; i <= N; i++) {
		cin >> mat[i];
	}
	sort(mat, mat + N + 1); //구멍난 곳을 오름차순으로 정렬


	min = mat[1]; //가장 왼쪽에 있는 값을 min으로 설정


	//N개의 구멍난 곳을 조사
	for (int i = 1; i <= N; i++) {
		//구멍사이의 간격보다 테이프의 길이가 짧으면 최솟값을 길어진 순간의 구멍으로 둔다. 테이프의 양 끝을 0.5만큼 주어 실제적으로 구멍을 덮는 부분은 L - 1이다. 
		if (mat[i] - min > L - 1) {
			min = mat[i];
			cnt++; //테이프의 갯수 증가
		}
	}
    
	cout << cnt;
}