[C++] 백준(BOJ) - 1911 : 흙길 보수하기

19 Mar 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 1911 : 흙길 보수하기(링크)

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

알고리즘

1. 정렬
2. 라인스위핑

풀이

• 물웅덩이를 순차적으로 탐색하기 위해 정렬 사용
• idx (널판지 끝의 값을 가리키는 변수)를 활용하여 라인스위핑
  • idx가 물웅덩이 시작지점 왼쪽에 있는 경우와 오른쪽에 있는 경우 두 가지로 나눠서 생각한다

코드

// BOJ-1911 : 흙길 보수하기
#include <bits/stdc++.h>
using namespace std;

int n, l, res;

vector<pair<int, int>> v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> l;

	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	int idx = 0, b;
	for (int i = 0; i < n; i++)
	{
		// idx 가 각 웅덩이 끝지점보다 뒤에 있으면 다음 웅덩이로 넘어감
		if (v[i].second <= idx) continue;

		// idx가 웅덩이 시작점보다 왼쪽에 있을 때
		if (idx < v[i].first)
		{
			b = (v[i].second - v[i].first) / l + ((v[i].second - v[i].first) % l ? 1 :0); // 나누어 떨어지면 0, 나머지 남으면 1
			idx = v[i].first + b * l;
		}
		// idx가 웅덩이 시작점보다 오른쪽에 있을 때
		else
		{
			b = (v[i].second - idx) / l + ((v[i].second - idx) % l ? 1 : 0);
			idx = idx + b * l;
		}
		res += b;
	}

	cout << res << '\n';
	return 0;
}

평가

• 정렬과 라인스위핑은 세트로 생각
• idx 기반 탐색
• 시작 지점 기준으로 나눠서 생각하기 (케이스 바이 케이스 따져 나가기)