반응형
https://www.acmicpc.net/problem/1911
이미 막힌 웅덩이일 경우만 생각해주면 어렵지 않은 문제이다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int M, woodLen, res = 0;
vector<pair<int, int> > v;
cin >> M >> woodLen;
for (int i = 0; i < M; i++) {
pair<int, int> input;
cin >> input.first >> input.second;
v.push_back(input);
}
sort(v.begin(), v.end());
int startIdx = -1;
for (int i = 0; i < M; i++) {
if (startIdx >= v[i].second) // 이미 널빤지로 막힌 웅덩이면
continue;
startIdx = max(startIdx, v[i].first);
int dist = v[i].second - startIdx;
if (dist % woodLen)
dist += woodLen - dist % woodLen;
startIdx += dist;
res += dist / woodLen;
}
cout << res;
}
반응형
'<algorithm> > 백준' 카테고리의 다른 글
백준 2230 수 고르기 c++ (0) | 2023.11.04 |
---|---|
백준 20310 타노스 c++ (1) | 2023.10.24 |
백준 1459 걷기 c++ (0) | 2023.10.12 |
백준 2879 코딩은 예쁘게 c++ (1) | 2023.10.09 |
백준 1026 보물 c++ (1) | 2023.10.05 |