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

문제링크 : https://www.acmicpc.net/problem/25972

25972번: 도미노 무너트리기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii> v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, cnt = 1; //기본값은 1
    cin >> N;
    for(int i=0; i<N; i++)
    {
        int x, l;
        cin >> x >> l;
        v.push_back({x, l});
    }

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

    for(int i=1; i<N; i++)
    {
        if(v[i-1].first + v[i-1].second >= v[i].first) continue; //구간이 겹치면 카운트 스킵
        cnt++; //새로운 구간이므로 카운트
    }

    cout << cnt;

    return 0;
}

정렬해서 풀면되는 크게 어렵지 않은 문제이다.

x좌표 기준으로 정렬을 하고 새로운 좌표가 직전 도미노의 x좌표 + 길이 값에 겹치는지 안겹치는지 확인하면 된다.

 

겹친다면 도미노가 이어지는 것이므로 앞에것만 건드려도 이어서 무너지므로 카운팅을 계속할 필요가 없다.

하지만 겹치지 않는다면 도미노가 이어지지 않는 새로운 구간이므로 다시 처음부터 무너트려야 하기에 카운팅을 해줘야 한다.