[백준 - 1449] 수리공 항승

||문제 이해

무한한 자를 수 없는 테이프를 가지고 구멍을 메꿔라

 

---

||해결 계획

물이 새는 위치를 오름차순으로 정렬하고 - O(n log n)

 

순차적으로 탐색하면서 구멍의 위치와 테이프의 길이를 더하여 그 안에 속한 구멍은 패스한다. - O(n)

= O(n log n + n) = O(n log n)

 

---

||계획 검증

1000 * log 1000 이므로 1초내에 충분히 끝날것이다.

 

---

||구현

#include <bits/stdc++.h>
using namespace std;

int arr[1001];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int n, l; cin >> n >> l;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);

	int cnt = 0;
	int end = 0;
	for (int i = 0; i < n; ++i)
	{
		end = arr[i] + l;
		++cnt;
		while(arr[i + 1] < end && arr[i + 1] != 0)
		{
			++i;
		}
	}

	cout << cnt;
	return 0;
}

 

---

||되돌아 보기

먼저 겹치는 부분은 의미가 없어서 생각에서 제외했고

해결 방법은 테이프는 자를수 없기 때문에 한번 붙일 때 최대한 많은 구멍을 메꾸는 것이다.

 

이러한 전략을 반복적으로 취해도 문제가 없다면 그리디를 사용하는게 좋을것 같아 그리디를 선택했다.

---

||개선 코드

#include<cstdio>
int main() {
	bool a[1001] = { 0 };
	int n, l;
	scanf("%d%d", &n,&l);
	while (n--)
	{
		int x;
		scanf("%d", &x);
		a[x] = 1;
	}
	int cnt = 0;
	for (int i = 1; i <= 1000; i++)
	{
		if (a[i])
		{
			cnt++;
			i += l-1;
		}
	}
	printf("%d", cnt);
}

다른 분의 코드이다.

시간 복잡도도 O(N)이며 공간 복잡도도 int형 배열이 아닌 bool형 배열을 사용하여 반으로 낮췄다.

 

위치를 int배열로 저장하는게 아닌 bool형 배열에 있다 없다로 저장하여 sort연산을 생략하였다!

bool형 배열을 하나의 파이프로 본것이다! 약간 지렸다...

 

그리고 다음 반복문에서 구멍을 찾는다면 카운팅 후 탐색 인덱스를 테이프 길이만큼 추가해

그 후에 나오는 구멍을 찾게하여 많은 불필요한 연산을 생략했다!

 

굉장히 배울게 많은 코드였다.