❯ g++ --version
 
Apple clang version 15.0.0 (clang-1500.1.0.2.5)
Target: arm64-apple-darwin23.2.0
Thread model: posix
 
# compile
❯ g++ -g -Wall -std=c++17 -o <file_name> <file_name>.cpp

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v;
 
void recur(int s, int e) {
    if (s >= e) return;
    // NOTE : 노드가 1개라면 그냥 탐색하면 된다
    if (s == e-1) {
        cout << v[s] << '\n';
        return;
    }
 
    int idx = s+1;
    // NOTE : 왼쪽 서브트리에 해당하는 인덱스 범위를 찾는다
    while (idx < e) {
        if (v[s] < v[idx]) break;
        ++idx;
    }
 
    // NOTE : 후위 순회 : 왼쪽 - 오른쪽 - 루트
    recur(s+1, idx); recur(idx, e); cout << v[s] << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    int x;
    while (cin >> x) { v.push_back(x); }
    recur(0, v.size());
    return 0;
}
 

map[i][j] = min(map[i-1][j], min(map[i][j-1], map[i-1][j-1])) + 1;

#include <iostream>
using namespace std;
#define MAX 1001
int n,m;
int map[MAX][MAX];
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> n >> m;
 
    char c;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            cin >> c;
            map[i][j] = c - '0';
        }
    }
 
    int ans = 0;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            if (map[i][j] == 0) continue;
            map[i][j] = min(
                map[i-1][j],
                min(map[i][j-1], map[i-1][j-1])
            ) + 1;
            ans = max(ans , map[i][j]);
        }
    }
    cout << ans*ans;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
int N;
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N;
    // NOTE : 최소힙
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int i=0; i<N; ++i) {
        ll x; cin >> x; pq.push(x);
    }
 
    ll ans = 0;
    while (pq.size() > 1) {
        ll t1 = pq.top(); pq.pop();
        ll t2 = pq.top(); pq.pop();
        ans += t1+t2;
        pq.push(t1+t2);
    }
    cout << ans;
 
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> Minus, Plus;
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N;
 
    for (int i=0; i<N; ++i) {
        int x; cin >> x;
        if (x <= 0) Minus.push_back(x);
        else Plus.push_back(x);
    }
 
    sort(Minus.begin(), Minus.end(), less<int>());
    sort(Plus.begin(), Plus.end(), greater<int>());
 
    int ans = 0;
 
    // NOTE : 짝으로 처리하기 때문에 홀수 길이인 경우 마지막 원소를 미리 추가
    if (Minus.size() & 1) ans += Minus.back();
    for (int i=0; i< (int)Minus.size()-1; i+=2) {
        ans += Minus[i] * Minus[i+1];
    }
 
    if (Plus.size() & 1) ans += Plus.back();
    for (int i=0; i< (int)Plus.size()-1; i+=2) {
        // NOTE : 1일 경우 더하는 것이 더 크다
        if (Plus[i+1] == 1) ans += Plus[i] + Plus[i+1];
        else ans += Plus[i] * Plus[i+1];
    }
 
    cout << ans;
    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N;
int alpha_cnt[26];
 
bool cmp(int a, int b) {
    return a > b;
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    
    cin >> N;
    string s;
 
    for (int i=0; i<N; ++i) {
        cin >> s;
        int p = 1;
        for (int j=s.length()-1; j>=0; --j) {
            alpha_cnt[s[j] - 'A'] += p;
            p *= 10;
        }
    }
 
    sort(alpha_cnt, alpha_cnt+26, cmp);
 
    int ans = 0;
    int d = 9;
    for (int i=0; i<26; ++i) {
        if (alpha_cnt[i] == 0) continue;
 
        ans += alpha_cnt[i] * d;
        --d;
    }
    cout << ans;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 10
#define ISLAND_MAX 7
 
struct pos {
    int y; int x;
};
 
struct tbridge {
    int len; int start; int end;
};
 
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
 
int N,M;
int map[MAX][MAX];
int island[MAX][MAX];
bool visited[MAX][MAX];
int island_cnt = 0;
vector<pos> land;
vector<tbridge> bridge;
int parent[ISLAND_MAX];
 
bool check_bound(int y, int x) {
    return y>=0 && y<N && x>=0 && x<M;
}
 
bool check(int y, int x) {
    return check_bound(y, x) && !visited[y][x] && map[y][x] == 1;
}
 
// NOTE : bfs를 하며 각 섬마다 id (island_cnt)를 부여한다
void numbering_island() {
    for (int i=0; i<land.size(); ++i) {
        int _y = land[i].y, _x = land[i].x;
 
        if (visited[_y][_x]) continue;
 
        queue<pos> q;
        visited[_y][_x] = true;
        island[_y][_x] = ++island_cnt;
        q.push({_y, _x});
 
        while (!q.empty()) {
            int y = q.front().y, x = q.front().x;
            q.pop();
 
            for (int i=0; i<4; ++i) {
                int ny=y+dy[i], nx=x+dx[i];
                if (!check(ny, nx)) continue;
 
                visited[ny][nx] = true;
                island[ny][nx] = island_cnt;
 
                q.push({ny, nx});
            }
        }
    }
}
 
void make_bridge() {
    // NOTE : 모든 땅 좌표를 순회하며 가능한 다리들을 모두 계산
    for (int i=0; i<land.size(); ++i) {
        int y=land[i].y, x=land[i].x;
        int start_island_id = island[y][x];
 
        for (int d=0; d<4; ++d) {
            int ny=y, nx=x;
            int len = 0;
 
            while (1) {
                ny += dy[d]; nx += dx[d];
 
                /**
                 * NOTE
                 * - 경계, 길이, 바다 위에 있는지 여부를 체크
                 * - 0은 바다, 1은 땅을 의미한다.
                */
                if (check_bound(ny, nx)) {
                    if (map[ny][nx] == 0) ++len;
                    else if (
                        map[ny][nx] == 1 &&
                        len>=2 &&
                        start_island_id != island[ny][nx]
                    ) {
                        bridge.push_back({len, start_island_id, island[ny][nx]});
                        break;
                    }
                    else break;
                }
                else break;
            }
        }
    }
}
 
int find(int a) {
    if (parent[a] == a) return a;
    return (parent[a] = find(parent[a]));
}
 
// NOTE : 다리 id 값이 작은 쪽을 부모로
void uni(int a, int b) {
    int pa = find(a);
    int pb = find(b);
 
    if (pa == pb) return;
 
    if (pa < pb) parent[pb] = pa;
    else parent[pa] = pb;
}
 
bool has_same_parent(int a, int b) {
    return find(a) == find(b);
}
 
bool b_cmp(tbridge& a, tbridge& b) { return a.len < b.len; }
 
int answer() {
    // NOTE : 다리 길이 최소합을 얻어야 한다
    sort(bridge.begin(), bridge.end(), b_cmp);
 
    for (int i=1; i<=island_cnt; ++i) {
        parent[i] = i;
    }
 
    int total_len = 0;
    for (int i=0; i<bridge.size(); ++i) {
        // NOTE : 연결되어 있지 않은 섬들에 대해 union 연산을 진행
        if (!has_same_parent(bridge[i].start, bridge[i].end)) {
            uni(bridge[i].start, bridge[i].end);
            total_len += bridge[i].len;
        }
    }
 
    // NOTE : 다리 id 값이 작은 쪽을 부모로 뒀기 때문에 1이 아니면 연결될 수 없음을 뜻함
    for (int i=1; i<=island_cnt; ++i) {
        if (find(i) != 1) {
            return -1;
        }
    }
 
    return total_len;
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N >> M;
    
    for (int i=0; i<N; ++i) {
        for (int j=0; j<M; ++j) {
            // NOTE : 0은 바다, 1은 땅을 의미한다.
            cin >> map[i][j];
            if (map[i][j] == 1) {
                // NOTE : bridge 후보군들을 만들기위해 완탐하기 때문에 땅들의 좌표를 미리 확보
                land.push_back({i, j});
            }
        }
    }
 
    numbering_island();
    make_bridge();
    cout << answer();
 
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
#define MAX 20
 
int N,M,sy,sx,K;
int map[MAX][MAX];
// NOTE : 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4로 주어진다.
int dy[] = {0, 0, 0, -1, 1};
int dx[] = {0, 1, -1, 0, 0};
int dice[7];
 
bool check(int y, int x) {
    return y>=0 && y<N && x>=0 && x<M;
}
 
void move(int dir) {
    int d1=dice[1], d2=dice[2], d3=dice[3], d4=dice[4], d5=dice[5], d6=dice[6];
 
    // 동
    if (dir == 1) {
        dice[1] = d4; dice[3] = d1; dice[6] = d3; dice[4] = d6;
        return;
    }
 
    // 서
    if (dir == 2) {
        dice[1] = d3; dice[3] = d6; dice[6] = d4; dice[4] = d1;
        return;
    }
 
    // 북
    if (dir == 3) {
        dice[1] = d5; dice[2] = d1; dice[6] = d2; dice[5] = d6;
        return;
    }
 
    // 남 (dir == 4)
    dice[1] = d2; dice[2] = d6; dice[6] = d5; dice[5] = d1;
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N >> M >> sy >> sx >> K;
 
    for (int i=0; i<N; ++i) {
        for (int j=0; j<M; ++j) {
            cin >> map[i][j];
        }
    }
 
    int dir;
    int y=sy, x=sx;
 
    // NOTE : K번에 걸쳐서 주사위를 굴린다
    while (K--) {
        cin >> dir;
        int ny=y+dy[dir], nx=x+dx[dir];
 
        // NOTE : 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 한다
        if (!check(ny, nx)) continue;
 
        move(dir);
 
        // NOTE : 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다.
        if (map[ny][nx] == 0) map[ny][nx] = dice[6];
        // NOTE : 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다.
        else {
            dice[6] = map[ny][nx];
            map[ny][nx] = 0;
        }
 
        // NOTE : 주사위를 굴리고 윗면을 출력
        cout << dice[1] << '\n';
        y = ny; x = nx;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 50
#define MAX_VIRUS 2500
 
struct pos {
    int y; int x;
};
 
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
vector<pos> virus;
vector<pos> activated;
bool visited[MAX_VIRUS];
 
int N,M;
int lab[MAX][MAX];
int time_map[MAX][MAX];
int ans = INT_MAX;
 
int empty_cnt = 0;
int infect_cnt = 0;
 
bool check(int y, int x) {
    return y>=0 && y<N && x>=0 && x<N &&
        (lab[y][x] != 1) && (time_map[y][x] == -1);
}
 
int bfs() {
    infect_cnt = 0;
 
    /**
     * NOTE
     * -1로 처음에 갱신하여 바이러스가 확산되지 않았음을 표기
    */
    memset(time_map, -1, sizeof(time_map));
 
    queue<pos> q;
    for (const auto& p : activated) {
        q.push(p);
        time_map[p.y][p.x] = 0;
    }
 
    int time = 0;
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int y = p.y, x = p.x;
 
        for (int i=0; i<4; ++i) {
            int ny=y+dy[i], nx=x+dx[i];
 
            if (!check(ny, nx)) continue;
 
            time_map[ny][nx] = time_map[y][x] + 1;
 
            /**
             * NOTE
             * - 빈땅이었을 때에만 bfs가 리턴하는 time을 갱신한다
             * - 이미 바이러스가 있는 칸 (2) 일 경우에는 시간이 소요되지 않는다
            */
            if (lab[ny][nx] == 0) {
                ++infect_cnt;
                time = time_map[ny][nx];
            }
 
            q.push({ny, nx});
        }
    }
    return time;
}
 
void dfs(int x, int cnt) {
    if (cnt == M) {
        int t = bfs();
 
        // NOTE : 모든 빈 칸에 확산되지 않았다면 최소 시간 갱신 x
        if (empty_cnt == infect_cnt) ans = min(t, ans);
        return;
    }
 
    for (int i=x; i<virus.size(); ++i) {
        if (visited[i]) continue;
        visited[i] = true; activated.push_back(virus[i]);
        dfs(i, cnt+1);
        visited[i] = false; activated.pop_back();
    }
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N >> M;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            cin >> lab[i][j];
 
            // NOTE : virus 위치를 미리 저장해 놓는다
            if (lab[i][j] == 2) virus.push_back({i, j});
 
            // NOTE : 모든 빈칸에 확산되었는지 확인하기 위해 빈칸의 개수를 세놓는다
            else if (lab[i][j] == 0) ++empty_cnt;
        }
    }
 
    dfs(0, 0);
    if (ans == INT_MAX) ans = -1;
    cout << ans;
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <deque>
using namespace std;
#define BOARD_MAX 101
 
struct snake {
    int y; int x;
};
 
// NOTE : Up, Down, Left, Right 순서
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
 
int N,K,L;
unordered_map<int, char> time_to_dir;
bool apple[BOARD_MAX][BOARD_MAX];
 
// NOTE : front: 꼬리, back: 머리
deque<snake> dq;
// NOTE : 뱀은 처음에 오른쪽을 향한다.
int dir=3;
bool game_over;
 
int dir_converter(char c) {
    if (c == 'L') {
        if (dir == 0) return 2;
        if (dir == 1) return 3;
        if (dir == 2) return 1;
        if (dir == 3) return 0;
    }
 
    if (c == 'D') {
        if (dir == 0) return 3;
        if (dir == 1) return 2;
        if (dir == 2) return 0;
        if (dir == 3) return 1;
    }
 
    return -1;
}
 
bool check_bound(int y, int x) {
    return y>=1 && y<=N && x>=1 && x<=N;
}
 
bool check_itself(int y, int x) {
    for (const auto& p : dq) {
        if (p.y == y && p.x == x) return false;
    }
    return true;
}
 
void rotate(int time) {
    char l_or_d = time_to_dir[time];
    dir = dir_converter(l_or_d);
}
 
void move() {
    // NOTE : dq.back == 머리, dq.front == 꼬리
    int ny = dq.back().y+dy[dir], nx = dq.back().x+dx[dir];
    
    // NOTE : 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다
    if (!check_bound(ny, nx) || !check_itself(ny, nx)) {
        game_over = true;
        return;
    }
 
    dq.push_back({ny, nx});
 
    // NOTE : 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다
    if (apple[ny][nx]) {
        apple[ny][nx] = false;
    }
    // NOTE : 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
    else {
        for (int i=0; i<dq.size()-1; ++i) {
            dq[i].y = dq[i+1].y;
            dq[i].x = dq[i+1].x;
        }
        dq.pop_back();
    }
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N >> K;
    int r,c;
    for (int i=0; i<K; ++i) {
        cin >> r >> c;
        apple[r][c] = true;
    }
    cin >> L;
    int t; char d;
    for (int i=0; i<L; ++i) {
        cin >> t >> d;
        time_to_dir.insert({t, d});
    }
 
    int time = 0;
    dq.push_back({1, 1});
    while (1) {
        game_over = false;
 
        // NOTE : 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다
        move();
        ++time;
 
        if (game_over) break;
 
        // NOTE : 방향을 전환해야 하는 순간이면 전환한다
        if (time_to_dir.find(time) != time_to_dir.end()) rotate(time);
    }
    cout << time;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define PLANE_MAX 11
using namespace std;
int dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 
 
int N,M,K;
 
// NOTE : 매 겨울 채워지는 양분의 양
int plane[PLANE_MAX][PLANE_MAX];
 
// NOTE : 각 칸의 양분 상태
int nutrient[PLANE_MAX][PLANE_MAX];
 
/**
 * NOTE
 * - 각 칸에는 여러 개의 나무가 담길 수 있다
 * - 나무의 나이가 담기게 된다
*/
vector<int> tree[PLANE_MAX][PLANE_MAX];
 
bool age_cmp(int a1, int a2) {
    return a1 < a2;
}
 
bool check_bound(int y, int x) {
    return y>=1 && y<=N && x>=1 && x<=N;
}
 
void spring_and_summer() {
    // spring
    for (int y=1; y<=N; ++y) {
        for (int x=1; x<=N; ++x) {
            if (tree[y][x].empty()) continue;
 
            // NOTE : 가장 어린 나무가 먼저 양분을 먹는다
            sort(tree[y][x].begin(), tree[y][x].end(), age_cmp);
 
            // NOTE : 양분을 섭취하고 나이가 먹은 나무들의 나이가 담긴다
            vector<int> tmp;
 
            int die = 0;
 
            for (int i=0; i<tree[y][x].size(); ++i) {
                int age = tree[y][x][i];
 
                if (nutrient[y][x] < age) {
                    die += age/2;
                }
                else {
                    nutrient[y][x] -= age;
                    tmp.push_back(age+1);
                }
            }
 
            tree[y][x].clear();
            for (const auto& n : tmp) {
                tree[y][x].push_back(n);
            }
 
            // summer
            nutrient[y][x] += die;
        }
    }
}
 
void fall() {
    for (int y=1; y<=N; ++y) {
        for (int x=1; x<=N; ++x) {
            if (tree[y][x].empty()) continue;
 
            for (int t=0; t<tree[y][x].size(); ++t) {
                // NOTE : 나이가 5의 배수여야 번식 가능하다
                if (tree[y][x][t]%5 != 0) continue;
 
                for (int i=0; i<8; ++i) {
                    int ny=y+dy[i], nx=x+dx[i];
                    if (!check_bound(ny, nx)) continue;
                    tree[ny][nx].push_back(1);
                }
            }
        }
    }
}
 
void winter() {
    for (int i=1; i<=N; ++i) {
        for (int j=1; j<=N; ++j) {
            nutrient[i][j] += plane[i][j];
        }
    }
}
 
int answer() {
    int cnt = 0;
    for (int i=1; i<=N; ++i) {
        for (int j=1; j<=N; ++j) {
            if (tree[i][j].empty()) continue;
            cnt += tree[i][j].size();
        }
    }
    return cnt;
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N >> M >> K;
    for (int i=1; i<=N; ++i) {
        for (int j=1; j<=N; ++j) {
            cin >> plane[i][j];
            nutrient[i][j] = 5;
        }
    }
 
    int y,x,age;
    for (int i=0; i<M; ++i) {
        cin >> y >> x >> age;
        tree[y][x].push_back(age);
    }
 
    while (K--) {
        spring_and_summer();
        fall();
        winter();
    }
    cout << answer();
    return 0;
}

int N,M;
struct pos {
    int y; int x;
};
vector<pos> home, chicken;
 
...
 
cin >> N >> M;
for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) {
        int t; cin >> t;
        if (t == 1) home.push_back({i, j});
        else if (t == 2) chicken.push_back({i, j});
    }
}

// main
dfs(0, 0);
 
 
...
 
int ans = INT_MAX;
vector<pos> choose;
bool check[MAX];
 
int dist(const pos& p1, const pos& p2) {
    return abs(p1.y - p2.y) + abs(p1.x - p2.x);
}
 
int cal() {
    int sum = 0;
    for (int i=0; i<home.size(); ++i) {
        int tmp = INT_MAX;
        for (int j=0; j<choose.size(); ++j) {
            tmp = min(tmp, dist(home[i], choose[j]));
        }
        sum += tmp;
    }
    return sum;
}
 
void dfs(int cur, int cnt) {
    if (cnt == M) {
        ans = min(ans, cal());
        return;
    }
 
    for (int i=cur; i<chicken.size(); ++i) {
        if (check[i]) continue;
        choose.push_back(chicken[i]); check[i] = true;
        dfs(i, cnt+1);
        choose.pop_back(); check[i] = false;
    }
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define MAX 13
using pii = pair<int, int>;
struct pos {
    int y; int x;
};
vector<pos> home, chicken;
vector<pos> choose;
 
bool check[MAX];
 
int N,M;
int ans = INT_MAX;
 
int dist(const pos& p1, const pos& p2) {
    return abs(p1.y - p2.y) + abs(p1.x - p2.x);
}
 
int cal() {
    int sum = 0;
    for (int i=0; i<home.size(); ++i) {
        int tmp = INT_MAX;
        for (int j=0; j<choose.size(); ++j) {
            tmp = min(tmp, dist(home[i], choose[j]));
        }
        sum += tmp;
    }
    return sum;
}
 
void dfs(int cur, int cnt) {
    if (cnt == M) {
        ans = min(ans, cal());
        return;
    }
 
    for (int i=cur; i<chicken.size(); ++i) {
        if (check[i]) continue;
        choose.push_back(chicken[i]); check[i] = true;
        dfs(i, cnt+1);
        choose.pop_back(); check[i] = false;
    }
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N >> M;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            int t; cin >> t;
            if (t == 1) home.push_back({i, j});
            else if (t == 2) chicken.push_back({i, j});
        }
    }
    dfs(0, 0);
    cout << ans;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
 
int N;
vector<pii> v;
priority_queue<int, vector<int>, greater<int>> pq;
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N;
    int s,t;
    for (int i=0; i<N; ++i) {
        cin >> s >> t;
        v.push_back({s, t});
    }
    // NOTE : 수업의 시작 시간을 기준으로 오름차순 정렬한다
    sort(v.begin(), v.end());
 
    // NOTE : 첫번째 수업은 강의실에 넣고 시작
    pq.push(v[0].second);
 
    for (int i=1; i<N; ++i) {
        int t = pq.top();
        // NOTE : 똑같은 강의실에 넣을 수 있다 (다음 수업 시작 시간 >= 현재 수업 끝나는 시간)
        if (v[i].first >= t) pq.pop();
        pq.push(v[i].second);
    }
 
    // NOTE : 큐에서 pop되지 못하고 남아있는 끝나는 시간 개수만큼 답이다
    cout << pq.size();
    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
#define MAX 100
using ll = long long;
 
int map[MAX][MAX];
ll dp[MAX][MAX];
int N;
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    cin >> N;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            cin >> map[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
 
    /** NOTE : 시작점의 dp값을 1로 설정한다 */
    dp[0][0] = 1;
    for (int y=0; y<N; ++y) {
        for (int x=0; x<N; ++x) {
            /**
             * NOTE
             * - dp값이 갱신이 되지 않았다면 도달하지 못하는 경로이므로 패스한다
             * - 종착역이면 패스한다
            */
            if (dp[y][x] == 0 || (y == N-1 && x == N-1)) continue;
 
            int d = map[y][x];
            /** NOTE : 미래의 dp값을 누적 갱신 */
            if (y+d < N) dp[y+d][x] += dp[y][x];
            if (x+d < N) dp[y][x+d] += dp[y][x];
        }
    }
 
    cout << dp[N-1][N-1];
    return 0;
}

#include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;
int choice[MAX];
bool visited[MAX];
bool cycle[MAX];
int n;
int cnt;
 
void dfs(int cur) {
    visited[cur] = true;
    int next = choice[cur];
    if (visited[next]) {
        // NOTE : 방문이 됐음에도 cycle로 마킹되지 않았어야만 사이클로 카운팅한다
        if (!cycle[next]) {
            for (int i=next; i!=cur; i=choice[i]) ++cnt;
            ++cnt;
        }
    }
    else dfs(next);
 
    /**
     * NOTE
     * - 선택한 학생에 대한 dfs를 끝내고 나서야 cycle 마킹
     * - 위에있는 cnt를 세는 부분에서 flag로 사용된다
    */
    cycle[cur] = true;
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
    int T; cin >> T;
    while (T--) {
        cin >> n;
        cnt = 0;
 
        for (int i=1; i<=n; ++i) {
            cin >> choice[i];
            visited[i] = cycle[i] = false;
        }
 
        for (int i=1; i<=n; ++i) {
            if (!visited[i]) dfs(i);
        } 
        cout << n-cnt << '\n';
    }
    return 0;
}

int N,M;
int map[MAX][MAX];
 
...
 
cin >> N >> M;
for (int i=0; i<N; ++i) {
    for (int j=0; j<M; ++j) {
        cin >> map[i][j];
    }
}

bool visited[MAX][MAX];
int ans = 0;
 
// void dfs(int y, int x, int cnt, int cur);
// void ooh(int y, int x);
 
...
 
for (int i=0; i<N; ++i) {
    for (int j=0; j<M; ++j) {
        visited[i][j] = true;
        dfs(i, j, 1, map[i][j]);
        visited[i][j] = false;
        // ㅜ
        ooh(i, j);
    }
}
cout << ans;

int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
int ans = 0;
bool visited[MAX][MAX];
 
...
 
bool check(int y, int x) {
    return y>=0 && y<N && x>=0 && x<M;
}
 
void dfs(int y, int x, int cnt, int cur) {
    if (cnt == 4) {
        ans = max(ans, cur);
        return;
    }
 
    for (int i=0; i<4; ++i) {
        int ny = y+dy[i], nx = x+dx[i];
        if (!check(ny, nx) || visited[ny][nx]) continue;
 
        visited[ny][nx] = true;
        dfs(ny, nx, cnt+1, cur+map[ny][nx]);
        visited[ny][nx] = false;
    }
}

void ooh(int y, int x) {
    int sum = map[y][x];
    int cnt = 0;
    int tmp = 1001;
    for (int i=0; i<4; ++i) {
        int ny = y+dy[i], nx = x+dx[i];
        if (!check(ny, nx)) continue;
        ++cnt;
        sum += map[ny][nx];
        tmp = min(tmp, map[ny][nx]);
    }
 
    if (cnt < 3) return;
    if (cnt == 3) {
        ans = max(ans, sum);
        return;
    }
 
    // cnt == 4
    ans = max(ans, sum - tmp);
}