[백준] 12914 곰을 위한 레스토랑

역시나 오늘도 문제 조건을 빼먹어서 틀렸다 ㅎㅎ 굿

곰은 1000마리 까지 들어오고 차이는 1백만 까지 들어온다

그럼 다 set에 넣고 확인해보면 된다

1. 먼저 set을 하나 만들어 주자

2. 곰의 위치 A[i]를 받자

3. set에서 A[i]-d에 대한 lower,upper_bound를 확인하자

4. lower는 같거나 && A[i]+d보다 같거나 커야한다

5. upper는 A[i]+d보다 같거나 크고 s.end()여야 한다

6. 만약 조건에 맞으면 출력 ㄱㄱ 하고 set.insert

7. 조건 틀리면 앞에서부터 찾아야 하므로 set 다 뒤지면서 똑같이 ㄱㄱ

8. 이 때 A[i]보다 같거나 커야한다 모든 위치는 ㅎㅎ(빼먹으면 틀림)

소스코드

#include <iostream>
#include <set>
using namespace std;
int n, d;
bool go(set<int>&s, int x) {
    int pos = x - d; 
    auto a = s.lower_bound(pos);
    if (*a != pos && *a<(x+d) && a !=s.end()) return false;
    a = s.upper_bound(pos);
    return (*a >= (x + d) || a==s.end());
}
int main() {
    set<int> s;
    scanf(" %d %d", &n, &d);
    for (int i = 0; i < n; i++) {
        int x; scanf(" %d", &x);
        if (go(s, x)) {
            printf("%d ", x); s.insert(x);
        }
        else {
            for (auto a = s.begin(); a != s.end(); a++) {
                int p = *a;
                if (p + d < x) continue;
                if (go(s, p + d)) {
                    printf("%d ", p+d); s.insert(p + d); break;
                }
            }
        }
    }
}