[Greedy] BOJ 1449번 : 수리공 항승

문제

---

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

 

입력

---

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

 

 

문제 요약

---

N 개의 구멍이 있는 파이프를 고치려고 한다. 테이프의 길이는 L 이고 구멍을 기준으로 좌우 0.5 의 여유를 두어서 붙여야 한다. 파이프의 최대길이는 1000이고 테이프는 겹치는것은 가능하지만 잘라서 사용할 순 없다.

 

풀이

---

 

 

특별히 주의 해야하는 부분은 아니지만 제가 자주 실수하는 부분을 말해볼까 합니다.

 

정말 초심자들만 보세요. ㅎ

주의사항 

 

 

1. 변수선언시 최대값을 여유롭게 설정하자. 

 

최대값이 1000이라고 하면 적어도 1005정도로 잡아주면 좋습니다.

 

2. 예제만 보고 풀려고 하지말자.

 

정말 제가 자주 하는 실수인데요....

예를들어 테이프의 길이를 2라고 예제에서 주어졌을때 테이프의 길이가 

항상 2라고 착각하는 경우가 종종 있습니다.

 

3. 입력받은 값을 반드시 사용하지는 않는다.

 

제가 몇번 풀면서 느낀거지만 시간복잡도가 엄청 크지 않다면

굳이 입력받은 인수로 크기를 설정하지 않아도 되는 경우가 종종 있습니다.

 

 

1. 우선 파이프(k)와 구멍난 곳을 체크할 배열(check) 두개를 선언합니다.

 

 

 

2. 입력받은 위치를 파이프 배열에 넣고 해당위치를 체크배열에 기록합니다.

 

EX) 1 ,5 의 위치에 구멍이 생겼다면

k[0] = 1 , k[1] = 5

check[1] = true, check[5] = true

 

 

 

3. 파이프 배열의 값을 정렬합니다.

 

정렬을 하는 이유는 테이프를 붙일때 항상 오른쪽으로만 길게 붙이기 때문입니다.

예를들어 길이가 5인 테이프가 있고 파이프[3] 위치에 붙이려고 합니다.

그러면 1 ~5 , 2~ 6, 3 ~ 7 등등 다양하게 붙일 수 있겠죠 ? 

하지만 저희는 그리디 알고리즘을 사용 할 예정이기 때문에 

무조건 3 ~ 7 방식으로 붙인다는 겁니다 .

 

 

 

4. 마지막으로 check 값이 true 라면

해당위치 부터 해당위치 + 테이프의 길이(L) -1 까지 check 를 false로 만들어 줍니다.

 

 

 

5. 4번을 반복하면서 count 값을 증가시킵니다.

 

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N, L;
	cin >> N >> L;
	int count=0;
	int k[1001];
	bool check[1001];
	for (int i = 0; i < N; i++) {
		cin >> k[i];
		check[k[i]] = true;
	}
	sort(k, k + N);

	for (int i = 0; i < N; i++) {
		if (check[k[i]]) {
			for (int j = k[i]; j <= min(k[i] + L - 1, 1001); j++)
				check[j] = false;
			count += 1;
		}
	}
	cout << count << '\n';
	return 0;

}