https://www.acmicpc.net/problem/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;
}
'백준' 카테고리의 다른 글
백준15953 - 상금 헌터 (0) | 2019.06.23 |
---|---|
백준9461 - 파도반 수열 (0) | 2019.06.22 |
백준5622 - 다이얼 (0) | 2019.06.19 |
백준3986 - 좋은단어 (0) | 2019.06.19 |
백준2870 - 수학숙제 (0) | 2019.06.19 |