문제 풀이 과정을 공유드린다.
문제 출처

1. 문제설명

• 1차원 배열의 맵에서 최소한의 널빤지 개수 계산
• 1 <=N<= 10,000개의 물 웅덩이
• 길이 L의 널빤지

• 물웅덩이에 대한 위치는 int, int로 주어짐

• 이건 여담인데, 예제를 보면 처음 좌표가 1~6이라서, 1 2 3 4 5 6 총 6칸인줄 알았음.
  • 근데… 문제의 힌트를 보면 1~6은 실제로 5칸이었음..
  • 흠터레스팅..

2. 알고리즘 설계

• int, int 이므로, pair<int, int>로 저장
• 웅덩이의 크기가 3이고, 주어진 널빤지가 2라면, 3/2=2.5개의 널빤지가 필요함.
  • 2.5개든 2.1개든 3개의 널빤지 필요
  • 올림 함수로 개수 계산
    • ceil(double num)

3. 로직

• 인덱스를 잘 이용해야 한다.
• 웅덩이 크기가 2고, 널빤지가 3이라면 웅덩이보다 넓은 범위를 커버했으므로,
  • 만약 커버해야할 영역을 이미 넘었다면, continue 해주고
  • 시작 위치보다는 크거나, 같거나, 적을 수 있기 때문에 max 함수를 통해 인덱스를 갱신시켜준다.

• 전체 코드

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

using pii = pair<int, int>;
int n, l;

int solution(vector<pii> v) {
	sort(v.begin(), v.end());

	int idx = 0, cnt = 0;
	for (pii p : v) {
		if (idx >= p.second)
			continue;

		idx = max(idx, p.first);
		double temp = double(p.second - idx) / l;
		cnt += ceil(temp);
		idx += ceil(temp) * l;
	}

	return cnt;
}

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

	cin >> n >> l;
	vector<pii> v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;

	cout << solution(v);
	return 0;
}

• 소감
  • 앞서 말한 1~6이 6칸인줄 알아서 조금 삽질을 많이했다..
  • 올림 함수 예전에 다른 사람 코드보고 정리해뒀었는데, 되게 유용한 스킬인듯..?