[C++][백준 25972] 도미노 무너트리기

문제

접근 방법

문제의 정답을 구하기 위해선 도미노가 무너지는 조건을 따르면 된다. 오른쪽으로 무너질 경우 좌표 값이 현재 좌표에 길이를 합친 값 이하일 경우 오른쪽으로 무너진다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int N, answer = 1;
vector<pii> v;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N;

    v = vector<pii>(N);

    for (pii &i : v)
    {
        cin >> i.first >> i.second;
    }

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

    pii prev = v.front();

    for (int i = 1; i < N; ++i)
    {
        pii cur = v[i];

        if (prev.first + prev.second < cur.first)
        {
            ++answer;
        }

        prev = cur;
    }

    cout << answer;
    return 0;
}

풀이

하나씩 무너진다는 점을 유의해야 한다.
즉 첫 번째 도미노가 모든 줄을 덮을 길이일지라도 가장 가까운 도미노 하나만을 무너뜨린다.

그렇기에 정렬을 하고 현재 도미노가 이전 도미노에 범위에 닿는지만 확인해 주면 된다.