[C++] 백준 1911 : 흙길 보수하기

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

1911번: 흙길 보수하기

 

1. 첫풀이, 입력예외사항처리(실제로 없었음)와 수학적인 계산 적용 없이 반복문으로만 풀었다. 172ms

풀고나니 다른 정답들과 시간 차이가 너무나서 재풀이 시도

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N, L;
vector<pair<int, int>> map;
int ans = 0;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		int a, b, c;
		cin >> a >> b;

        // a < b인 입력
		if(a>b){
			c = a;
			a = b;
			b = a;
		}
		map.push_back({ a, b });
	}

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

	int covered = -1, to = -1;
	for (int i = 0; i < map.size(); i++) {
		covered = covered > map[i].first ? covered : map[i].first;
		to = map[i].second;

		while (covered < to) {
			covered += L;
			ans++;
		}
	}

	cout << ans;

	return 0;
}

 

2. 재풀이, 입력예외상황처리 없애고 반복문을 수학적 계산 적용해서 생략했다. 4ms

그리디 알고리즘은 최대한 수학적풀이를 적용한 뒤 반복문을 사용해야할 듯..

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N, L, a, b;
vector<pair<int, int>> map;
int ans = 0;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		map.push_back({ a, b });
	}

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

	int covered = -1, to = -1;
	for (int i = 0; i < map.size(); i++) {
		covered = covered > map[i].first ? covered : map[i].first;
		to = map[i].second;

		int gap = to - covered;
		int tiles = (gap + L - 1) / L;
		ans += tiles;
		covered += (tiles*L);
	}

	cout << ans;

	return 0;
}