[C++] [골드 5] 1911번: 흙길 보수하기

링크

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

1911번: 흙길 보수하기

문제

입출력 예제

코드

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

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int answer = 0;

    int N; // 웅덩이 개수 
    int L; // 널빤지 길이

    vector<pair<int, int>> pool;

    cin >> N >> L;

    // 웅덩이 만드는 과정
    for (int i = 0; i < N; i++)
    {
        int start, end;
        cin >> start >> end;

        pool.push_back({start, end});
    }

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

    int pos = pool[0].first;
    for (int i = 0; i < pool.size(); i++)
    {
        if (pos > pool[pool.size()-1].second) break;

        // 만약 pos 위치가 구덩이 위치가 아니라면? pos를 구덩이의 처음 위치로 옮겨야지
        if (pos < pool[i].first)
        {
            pos = pool[i].first;
        }

        while (pos < pool[i].second)
        {
            pos += L;
            answer++;
        }
    }

    cout << answer;

    return 0;
}

풀이

폭우가 내려서 N개의 물웅덩이가 생겼다.

물웅덩이를 덮을 수 있는 길이가 L인 널빤지들을 가지고 있다.

물웅덩이들의 위치와 크기에 대한 정보가 주어질 때,
모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

 

>>

 

구덩이의 위치를 저장하기 위해서 pair형태로 벡터를 선언합니다.

 

이후 현재 널빤지가 막고있는 마지막 위치를 저장할 pos 를 선언합니다.

 

최초의 pos 위치는 처음 물 웅덩이의 시작 지점으로 설정하고,
널빤지의 길이인 L을 pos에 더합니다.

pos가 물 웅덩이를 모두 가리지 않았다면 while문으로 인해 pos에 L길이를 다시 더합니다.

만약 pos가 물 웅덩이의 종료 지점을 지났다면 다음 물 웅덩이의 시작위치를 체크해
pos가 물 웅덩이보다 이전에 있다면 pos를 물 웅덩이의 시작지점으로 옮기고
pos가 물 웅덩이 내부에 있다면 다시 이전의 과정을 반복합니다.