1911 - 흙길 보수하기

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

1911번: 흙길 보수하기

생각해보기

• 시작점을 옮겨가며 물웅덩이 범위를 넘을때 까지 널빤지를 쌓아도 된다.
• 더 빠르게 하려면 수학적 공식으로 바꿔서 생각해보자.
• 이전에 설치한 널빤지가 다음 웅덩이를 덮어줄 수도 있다.

코드

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

using namespace std;
typedef pair<int,int> PII;

int N, L;
vector<PII> swamp;

void input(){
    int a,b;
    cin>>N>>L;

    for(int i=0;i<N;++i){
        cin>>a>>b;
        swamp.push_back({a,b});
    }
    sort(swamp.begin(),swamp.end());
}

void solution(){
    int ans = 0, now = 0;
    for(int i=0;i<swamp.size();++i){
        if(now < swamp[i].first)
            now = swamp[i].first;

        int next = swamp[i].second;

        int num = ceil((double)(next-now)/L);
        ans += num;
        now += num * L;
    }
    cout<<ans<<'\n';
}

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

    input();
    solution();

    return 0;
}