[C++][백준 34139] 의식의 광장

문제

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

접근 방법

가장 뒤에 있는 빛이 가장 먼 거리를 이동한다면 겹치는 경우는 없을 것입니다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;

int H, N;
pii lights[200000];
int dists[200000];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> H >> N;
    for (int i = 0; i < N; ++i)
    {
        int c;
        cin >> c >> c;
        lights[i] = {c, i};
    }

    sort(lights, lights + N, greater<>());
    for (int i = 0; i < N; ++i)
    {
        const pii &light = lights[i];
        dists[light.second] = N - i;
    }

    cout << "YES\n";

    for (int i = 0; i < N; ++i)
    {
        const int &dist = dists[i];
        cout << dist << " ";
    }
    return 0;
}

풀이

빛을 위치를 기준으로 정렬을 한 뒤 가장 뒤에 있는 빛에 가장 긴 이동 거리를 배정하면 됩니다.

뒤에서부터 서로 다른 이동거리만큼 이동하기에 같은 열에 위치할 가능성은 없습니다. (같은 위치일 시 당연히 다른 열에 도착하고 다른 위치일 시 더 뒤에 있는 것이 더 뒤로 이동하기 때문입니다)