백준: Class 6 - 2533, 13334

</br> 클래스 5는 이제 플레티넘 5 문제들만 남아서, 클래스 6의 골드 문제들을 먼저 풀어 보자
</br>

2533: 사회망 서비스(SNS)

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

#include <bits/stdc++.h>

using namespace std;

vector<int> tree[1000001];
int dp[1000001][2];

int func(int now, int isEarly, int p){
    if( dp[now][isEarly] != -1 ) return dp[now][isEarly];
    dp[now][isEarly] = isEarly;
    for(int nx : tree[now]){
        if( nx == p ) continue;
        if( isEarly ) dp[now][isEarly] += min(func(nx, 0, now), func(nx, 1, now));
        else dp[now][isEarly] += func(nx, 1, now);
    }
    return dp[now][isEarly];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        dp[i][0] = -1;
        dp[i][1] = -1;
    }
    cout << min(func(1, 0, 0), func(1, 1, 0)) << endl;
}

나는 자꾸 dp를 만들어 놓고 dp 값이 있으면 리턴을 해 줘야 하는데 그걸 깜빡해서 시간 초과 났다 바보 주의하자

알고리즘은

1. 내가 얼리어답터면 자식들은 얼리어답터든 아니든 상관없다
2. 내가 얼리어답터가 아니면 자식들은 무조건 얼리어답터야 한다(내 친구들이 다 얼리어답터야 하니까)

따라서 dp[i][i가 얼리어답터일 때, 아닐 때] = i까지의 총 얼리어답터의 수로 저장한다.
자식 노드에서 부모 쪽으로 다시 가면 안 되므로, 재귀 함수 func(int now, int isEarly, int p)에 현재 탐색할 dp[now][isEarly]에 사용될 값들과 추가로 부모 노드 p도 인자로 넘겨준다.
</br>

13334: 철로

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

#include <bits/stdc++.h>

using namespace std;

vector< pair<int, int> > v;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, d;
    cin >> n;

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        if( a > b ) swap(a, b);
        v.push_back(make_pair(b, a));
    }
    cin >> d;

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

    int ans = 0, cnt = 0;
    priority_queue<int, vector<int>, greater<> > pq;
    if( v[0].first - d <= v[0].second ) pq.push(v[0].second);
    ans = max(ans, (int)pq.size());

    for(int i = 1; i < n; i++){
        int ms = v[i].first - d;
        while( pq.size() && pq.top() < ms ){
            pq.pop();
        }
        if( ms <= v[i].second ) pq.push(v[i].second);
        ans = max(ans, (int)pq.size());
    }

    cout << ans << endl;
}

라인 스위핑 문제다
처음에 O(N^2)로 제출하니까 시간 초과 난다. 당연하지
그래서, 직접 그림 그리면서 막 움직여 보니까 알겠더라

1. 오른쪽 점 기준으로 오름차순 정렬
2. 만약 현재 집-회사가 라인 안에 들어가면 우선순위 큐에 왼쪽 점 넣기
3. 다음으로 넘어감. 우선순위 큐의 탑이 넘어간 현재 라인의 최소보다 작다면 다 pop해서 없애줌 ```md ex) 백준 예제 8 5 40 35 25 10 20 10 25 30 50 50 60 30 25 80 100 30

큰 쪽을 b로 해서 (b, a)로 정렬 후: 20 10 25 10 30 25 35 25 40 5 50 30 60 50 100 80

20-30 = -10이 10보다 작으므로 라인 안에 들어 감. 우선순위 큐: 10

25-30 = -5가 10보다 작으므로 라인 안에 들어 감. 우선순위 큐: 10 10

30-30 = 0이 25보다 작으므로 라인 안에 들어 감. 우선순위 큐: 10 10 25

35-30 = 5가 25보다 작으므로 라인 안에 들어 감. 우선순위 큐: 10 10 25 25

40-30 = 10이 5보다 크므로 라인 안에 안 들어 감. 우선순위 큐: 10 10 25 25

50-30 = 20이 30보다 작으므로 라인 안에 들어 감. 우선순위 큐: 10 10 25 25 30 그런데, 우선순위 큐의 top()이 20보다 같거나 커질 때까지 pop() 우선순위 큐: 25 25 30

60-30 = 30이 50보다 작으므로 라인 안에 들어 감. 우선순위 큐: 25 25 30 50 그런데, 우선순위 큐의 top()이 30보다 같거나 커질 때까지 pop() 우선순위 큐: 30 50

100-30 = 70이 80보다 작으므로 라인 안에 들어 감. 우선순위 큐: 30 50 80 그런데, 우선순위 큐의 top()이 70보다 같거나 커질 때까지 pop() 우선순위 큐: 80

따라서 우선순위 큐의 맥스 사이즈는 4 ```
</br>

---

</br>