백준: Class 5 - 2568, 14939

</br> 클래스 5 마지막
</br>

2568: 전깃줄 - 2

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

#include <bits/stdc++.h>

using namespace std;

pair<int, int> line[100001];
pair<int, int> tracking[100001];
vector<int> ind;

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

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        line[i] = make_pair(a, b);
    }

    sort(line, line + n);

    ind.push_back(line[0].second);
    tracking[0] = make_pair(1, line[0].first);
    for(int i = 1; i < n; i++){
        int a = line[i].first;
        int b = line[i].second;
        if( b > ind.back() ){
            ind.push_back(b);
            tracking[i] = make_pair(ind.size(), a);
        }
        else{
            auto it = lower_bound(ind.begin(), ind.end(), b);
            *it = min(*it, b);
            tracking[i] = make_pair(it-ind.begin()+1, a);
        }
    }

    cout << n - ind.size() << '\n';

    stack<int> st;
    int t = ind.size();
    for(int i = n-1; i >= 0; i--){
        if( tracking[i].first == t ) t--;
        else st.push(tracking[i].second);
    }
    while( st.size() ){
        cout << st.top() << '\n';
        st.pop();
    }

}

처음 봤을 땐 겹치는 애들을 카운트해서 제일 많은 순으로 뺄까 했는데 n이 10만이기도 하고 복잡하다
그래서 교차 조건을 보니 (a,b)가 있으면 a보다 큰데 b보다 작거나, b보다 큰데 a보다 작거나 한 애들끼리 교차한다
따라서 왼쪽과 오른쪽이 모두 증가하는 수열이면 교차할 일이 없다!!
그러면 입력을 a 기준으로 정렬하고, b에서 가장 긴 증가하는 수열을 찾으면 된다.
저번 포스트(12015: 가장 긴 증가하는 부분 수열 2, https://cyj893.github.io/algorithm/Algorithm17_11/)처럼 구하면 되긴 한데, 걔네도 되추적해서 출력해야 한다
i부터 방문 순서는 대충

ex) 백준 예제
8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

 1 1
 1 2
 2 3
 1 4
 2 6
 3 7
 4 9
 5 10

이런 식으로 되므로, 밑에서부터 숫자가 작아지는 부분을 찾으면 된다.

 1 1      x
 1 2      x
 2 3      x
 1 4      <
 2 6      <
 3 7      <
 4 9      <
 5 10     <

</br>

14939: 불 끄기

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

#include <bits/stdc++.h>

using namespace std;

int mmap[12][12];
int t[12][12];
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};

void onoff(int x, int y){
    for(int i = 0; i < 5; i++){
        t[x+dx[i]][y+dy[i]] ^= 1;
    }
}

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

    for(int i = 1; i < 11; i++){
        string s;
        cin >> s;
        for(int j = 1; j < 11; j++){
            if( s[j-1] == 'O' ) mmap[i][j] = 1;
            else mmap[i][j] = 0;
        }
    }

    int ans = INT_MAX;
    onoff(1, 1);
    for(int bit = 0; bit < 1024; bit++){
        int cnt = 0;
        for(int i = 1; i < 11; i++){
            for(int j = 1; j < 11; j++){
                t[i][j] = mmap[i][j];
            }
        }
        for(int i = 1; i < 11; i++){
            if( bit & (1 << (i-1)) ){
                onoff(1, i);
                cnt++;
            }
        }
        for(int i = 2; i < 11; i++){
            for(int j = 1; j < 11; j++){
                if( t[i-1][j] ){
                    onoff(i, j);
                    cnt++;
                }
            }
        }
        bool chk = true;
        for(int i = 1; i < 11; i++){
            if( t[10][i] ){
               chk = false;
               break;
            }
        }
        if( chk ) ans = min(ans, cnt);
    }

    if( ans == INT_MAX ) ans = -1;
    cout << ans << endl;

}

10*10인 거 보니까 좀 다 해보는 경우일 것 같다 물론 2^100을 다 하지는 못 하는데
그런데 위에서 아래로 쭉 눌러 본다고 하면, 일단 첫 줄을 어떤 경우로 다 눌러 보면 어쩔 수 없이 켜진 게 남아 있을 수 있는데 그대로 넘어가야 할 때가 생긴다
그럼 그 아래 줄에서 걔네를 처리해 줘야 한다 아하 그럼 2^10가지만 다 해 볼까
즉

1. 첫 줄을 2^10 모든 경우를 다 해 보자
2. 각 경우마다 첫 줄에 남은 켜진 게 있으면 둘째 줄에서 걔네를 꺼주자
3. 그럼 또 셋째 줄에서 둘째 줄에 남은 켜진 걸 꺼주고 등등
4. 마지막 줄까지 다 했는데, 마지막에 또 남아 있으면 실패, 남은 게 없으면 성공
   </br>

---

클래스 5를 다 끝냈다~~~ 굿
</br>