백준 1911 C++

https://www.acmicpc.net/problem/1911

 

처음에 배열을 생각했는데 배열의 크기가 너무 크다고 안된다고 해서
sort해서 널빤지가 넘어가는 부분에 대해 생각한 후 계산해서 for문 돌리니까 맞았다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, l;	//n개의 웅덩이(1~10000), l의 길이 널빤지(1~1,000,000) 널빤지는 무한.
int s, e, maxe=0;
ll result = 0;
vector<pair<int, int>> v;

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

	cin >> n >> l;
	
	int s, e;
	for (int i = 0; i < n; i++) {
		cin >> s >> e;
		maxe = max(maxe, e);
		v.push_back({ s, e });
	}

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

	int nulend = -1;
	for (auto i : v) {
		int nows = i.first;							//널빤지를 세워야하는 시작점.
		if (i.second - 1 <= nulend) continue;		//널빤지가 끝난 자리보다 다음 웅덩이가 작으면 넘어간다.

		if (i.first <= nulend) {		//웅덩이의 첫 시작이 널빤지가 끝난 위치보다 작다. -> 널빤지가 살짝 걸쳐져있다.
			nows = nulend + 1;		
		}

		int tempResult;
		int here = i.second - nows;
		if (here % l == 0) {		//여기 웅덩이 크기로 널빤지를 뒀을 때 널빤지 크기가 딱 맞다.
			//cout << "int Same\n";
			tempResult = here / l;
			nulend = i.second - 1;		//널빤지의 끝의 위치가 i.second - 1이다. 
		}
		else {		//널빤지 크기가 더 남는다.
			//cout << "in not same'\n";
			tempResult = here / l + 1;
			int nulleft = l - (here % l);		//nulleft 만큼 남는다.
			nulend = i.second - 1 + nulleft;		//널빤지가 남은 만큼 널빤지의 끝자락을 더한다.
		}
		
		result += tempResult;
	}

	cout << result;
}