백준 2026년 3, 4주차 정리 노트

[G1~P5] 네트워크

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

A에서 B로 흐르는 간선(네트워크)가 여러 개일 수 있다.

간략화 연산을 수행하면 어떤 것들이 바뀌는지 확인한다.

• in-degree
• out-degree

언제 간략화가 가능한가? → $out$-$degree > 0\,\&\, in$-$degree > 0$

각 정점에 대한 불변량 : $outdeg(v) - indeg(v)$

 

[C++17 코드]

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  int n, m; cin >> n >> m;
  int inD[n +1]{}, outD[n + 1]{};
  for (int i = 0; i < m; i++) {
    int x, y; cin >> x >> y;
    inD[y]++;
    outD[x]++;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += max(0, outD[i] - inD[i]);
  cout << ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

 

[P2] 최소 체인 커버

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

최소 경로 커버 (Minimum Path Cover) — 모든 정점을 서로 겹치지 않게 최소 개수의 경로들로 분할하는 것 ⇒ 정점 수 - 최대 매칭으로 계산할 수 있다. (이분 매칭)

 

[C++17 코드]

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  int n, m; cin >> n >> m;
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; i++) {
    int x, y; cin >> x >> y;
    x--; y--;
    adj[x].push_back(y);
  }
  vector<bool> vis(n);
  vector<int> A(n, -1), B(n, -1);
  function<bool(int)> dfs = [&](int x) -> bool {
    vis[x] = 1;
    for (int i : adj[x]) {
      if (B[i] == -1 || (!vis[B[i]] && dfs(B[i]))) {
        A[x] = i;
        B[i] = x;
        return 1;
      }
    }
    return 0;
  };
  int ans = 0;
  for (int i = 0; i < n; i++) {
    fill(all(vis), 0);
    if (dfs(i) == 0) ans++;
  }
  cout << ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

 

[G3] Passport Control

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

승객은 $1, 2, …, N$ 순서로 $K$개의 창구 큐에 들어가게 된다.

한 창구의 큐에 들어있는 승객 번호는 항상 오름차순이다. ⇒ 나오는 순서는 증가 수열임

빠져 나온 순서 $\pi$ 는 최대 $K$개의 증가 부분수열 그룹으로 쪼갤 수 있어야 한다.

이를 $K$개의 모노톤 스택으로 관리해 풀 수 있다.

 

[C++17 코드]

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  int n, m; cin >> n >> m;
  stack<int> st[m];
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    bool flag = 0;
    for (int j = 0; j < m; j++) {
      if (st[j].empty() || st[j].top() < x) {
        st[j].push(x);
        flag = 1;
        break;
      }
    }
    if (!flag) {
      cout << "NO";
      return;
    }
  }
  cout << "YES";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

 

[G5] 광역기 맞으면 서렌하는 게임

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

못피하는 광역기를 하나 고정하고, 나머지 광역기를 모두 피할 수 있는지 시뮬레이션한다. (브루트포스 $O(N^2)$)

이제 이동해서 광역기를 피할 수 있는지 판단하는 방법이 중요하다.

현재 위치를 $[curL, curR]$, 다음 위치가 $[L_i, R_i]$ 일 때, $[curL - 1, curR + 1]$와 $[L_i, R_i]$의 교집합이 있는지 확인하면 된다. 그리고 다음 현재 위치는 그 교집합이 된다.

 

[C++17 코드]

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  int n; cin >> n;
  vector<pii> v(n);
  for (auto &[x, y] : v) cin >> x >> y;
  for (int k = 0; k < n; k++) {
    pii cur = k == 0 ? make_pair(-INF, INF) : v[0];
    bool ok = true;
    for (int i = 0; i < n; i++) {
      if (i > 0) cur = {cur.first - 1, cur.second + 1};
      if (i == k) continue;
      cur.first = max(cur.first, v[i].first);
      cur.second = min(cur.second, v[i].second);
      if (cur.first > cur.second) {
        ok = false;
        break;
      }
    }
    if (ok) {
      cout << "World Champion";
      return;
    }
  }
  cout << "Surrender";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}