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

문제 링크

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

---

◆문제 해결 및 설명◆

문제 : 물 웅덩이와 널빤지의 갯수와 첫 줄에 제공하고, 물 웅덩이의 길이를 제공할 때, 최소 널빤지 사용 갯수를 대답하라.

 

힌트를 보고 처음에는 아무생각 없이 구현으로 풀었다. 

그랬더니 바로 메모리 초과가 딴! (문제 풀기전에 메모리와 시간을 확인 해야겠죠?)

그럼 이걸 수학적으로 풀어야 한다고 생각이 들었고, 그럼 물 웅덩이의 시작 부분을 찾아서 널빤지를 깔고 널빤지가 끝나는 위치를 저장한 다음, 저장한 위치에다가 널판지를 계속 설치를 하고,

이후 다음 물 웅덩이의 시작 부분이 저장된 널빤지가 끝나는 위치보다 작다면 널빤지가 끝나는 위치부터 널판지를 설치하는 코드를 작성하였다.

 

◆코드 전문◆

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

int main()
{
    int N, L, answer = 0, maxLen = 0;
    cin >> N >> L;
    vector<pair<int, int>> pairArray(N);
    for (int i = 0; i < N; i++)
    {
        int start, end;
        cin >> start >> end;
        pairArray[i] = make_pair(start, end);
        maxLen = max(maxLen, end);
    }
    sort(pairArray.begin(), pairArray.end());

    int done = 0;
    for (int i = 0; i < pairArray.size(); i++)
    {
        int howNamu;
        if (done < pairArray[i].first)
        {
            howNamu = ceil((double)(pairArray[i].second - pairArray[i].first) / L);
            answer += howNamu;
            done = pairArray[i].first + howNamu * L;
        }
        else
        {
            howNamu = ceil((double)(pairArray[i].second - done) / L);
            answer += howNamu;
            done = done + howNamu * L;
        }
    }

    cout << answer;
}