제2회 유틸컵

• 제2회 유틸컵에 참가했다. 후기는 여기 참조.

BOJ 2206 : 벽 부수고 이동하기 (Gold 3)

• BFS 한 번 돌려서 벽에 걸리는 애들을 거리 오름차순 PQ에 저장해놓고 BFS 다 돌고 나서 그 PQ를 가지고 BFS를 한 번 더 돌리면 된다.
• PQ를 사용하는 이유는 기존에 BFS는 어차피 거리순 정렬이 되어 있으므로 그냥 큐를 사용하면 되지만, 벽에 걸리는 것을 저장하게 되면 각기 다른 거리 정보를 가졌기에 순차적으로 BFS를 돌기 위해선 PQ가 필요하다.

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

struct Node {
  int x, y, c;

  bool operator<(const Node& n) const {
    return c > n.c;
  }
};

const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int INF = 1000 * 1001;

bool maze[1000][1000];
bool visited[1000][1000] = {false, };
bool visited2[1000][1000] = {false, };

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  memset(visited, false, 1000 * 1000 * sizeof(bool));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      scanf("%1d", &maze[i][j]);

  queue<Node> q;
  priority_queue<Node> pq;
  q.emplace(0, 0, 1);
  visited[0][0] = true;

  int res = INF;
  while (!q.empty()) {
    auto [x, y, c] = q.front();
    q.pop();

    if (x == n-1 && y == m-1)
      res = min(res, c);

    for (auto [dx, dy] : d) {
      int nx = x + dx, ny = y + dy;
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (visited[nx][ny]) continue;
      visited[nx][ny] = true;

      if (maze[nx][ny]) {
        pq.emplace(nx, ny, c+1);
      } else {
        q.emplace(nx, ny, c+1);
      }
    }
  }

  while (!pq.empty()) {
    auto [x, y, c] = pq.top();
    pq.pop();

    if (x == n-1 && y == m-1)
      res = min(res, c);

    for (auto [dx, dy] : d) {
      int nx = x + dx, ny = y + dy;
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (visited2[nx][ny]) continue;

      if (!maze[nx][ny]) {
        visited2[nx][ny] = true;
        pq.emplace(nx, ny, c+1);
      }
    }
  }

  printf("%d", res == INF ? -1 : res);
  return 0;
}

BOJ 2252 : 줄 세우기 (Gold 3)

• 위상정렬 하면 된다.

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

using vi = vector<int>;

vector<vector<int>> gph;
vi topo;
vector<bool> visited;

void dfs(int x) {
  if (visited[x]) return;
  visited[x] = true;
  for (int y : gph[x])
    dfs(y);
  topo.push_back(x);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  gph.resize(n + 1);
  visited.resize(n + 1, false);

  for (int i=0;i<m;i++) {
    int a, b; cin >> a >> b;
    gph[a].push_back(b);
  }

  for (int i=1;i<=n;i++)
    dfs(i);

  for (auto it=topo.rbegin(); it<topo.rend(); it++)
    cout << *it << ' ';

  return 0;
}

BOJ 1967 : 트리의 지름 (Gold 4)

• 각 노드가 꼭지(LCA)일 때의 최대 길이를 저장하면 될 것 같다고 생각했다.
• 입력이 정렬되어 있길래 이대로 하면 된다고 생각했는데 depth가 정렬되어 있다는 보장이 없었다. 꼼꼼하게 생각하길...
• 입력을 다 받고 DFS를 돌려서 depth를 계산해두고, 이를 key로 해서 PQ를 돌려서 (일종의) BFS를 해서 각 노드가 꼭지일 때의 최대 길이를 구했다.

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

using pii = pair<int, int>;

struct Node {
  int depth, i, parent, weight;
  auto operator<=>(const Node&) const = default;
};

Node nodes[10001];
pii maxtwo[10001] = {}; // two largest children weight sum

int dfs(int x) {
  if (x == 1) return 0;
  return nodes[x].depth = dfs(nodes[x].parent) + 1;
}

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

  int n; cin >> n;
  priority_queue<Node> q;
  for (int i=2;i<=n;i++) {
    int par, child, weight; cin >> par >> child >> weight;
    nodes[child] = {-1, child, par, weight};
  }
  nodes[1] = {0, 1, 0, 0};
  for (int i=2;i<=n;i++)
    dfs(i);
  for (int i=1;i<=n;i++)
    q.push(nodes[i]);

  while (!q.empty()) {
    auto [_, i, par, w] = q.top();
    q.pop();

    int tar = maxtwo[i].first + w;
    if (tar > maxtwo[par].first) {
      maxtwo[par].second = maxtwo[par].first;
      maxtwo[par].first = tar;
    } else if (tar > maxtwo[par].second) {
      maxtwo[par].second = tar;
    }
  }

  int res = 0;
  for (int i=1;i<=n;i++)
    res = max(res, maxtwo[i].first + maxtwo[i].second);

  cout << res;

  return 0;
}

BOJ 14442 : 벽 부수고 이동하기 2 (Gold 3)

• BOJ 2206번과 크게 다르지 않다.
• 기존에 내 구현으로는 확장할 수 없어서 새로 짰다.

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

struct Node {
  int x, y, c, b;
};

const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int INF = numeric_limits<int>::max();

bool maze[1000][1000];
bool visited[1000][1000][11] = {false, };

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);

  memset(visited, false, 1000 * 1000 * sizeof(bool));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      scanf("%1d", &maze[i][j]);

  queue<Node> q;
  q.emplace(0, 0, 1, 0);
  visited[0][0][0] = true;

  int res = INF;
  while (!q.empty()) {
    auto [x, y, c, b] = q.front();
    q.pop();

    if (x == n-1 && y == m-1)
      res = min(res, c);

    for (auto [dx, dy] : d) {
      int nx = x + dx, ny = y + dy;
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (visited[nx][ny][b]) continue;
      visited[nx][ny][b] = true;

      if (maze[nx][ny]) {
        if (b < k)
          q.emplace(nx, ny, c+1, b+1);
      } else {
        q.emplace(nx, ny, c+1, b);
      }
    }
  }

  printf("%d", res == INF ? -1 : res);

  return 0;
}

BOJ 1644 : 소수의 연속합 (Gold 3)

• 에라토스테네스의 체를 돌리고 소수의 누적합을 구하고 투포인터로 돌리면 되는 것이었다.

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

#define sz(a) ((int)(a).size())

using ll = long long;

bitset<4'000'001> sieve;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  sieve.set();
  sieve[0] = sieve[1] = false;
  for (int i=2;i<=(int)sqrt(n);i++) {
    if (!sieve[i]) continue;
    for (int j=i*i;j<=n;j+=i)
      sieve[j] = false;
  }

  vector<ll> psum; psum.reserve(sieve.count()+1);
  ll ss = 0;
  psum.push_back(0);
  for (int i=2;i<=n;i++) {
    if (sieve[i]) {
      ss += i;
      psum.push_back(ss);
    }
  }

  int l=0, r=1;
  int ans=0;
  while (r < sz(psum) && l < r) { // is (l < r) necessary?
    int x = psum[r]-psum[l];
    if (x < n) {
      r++;
    } else if (x > n) {
      l++;
    } else {
      ans++;
      l++;
    }
  }

  cout << ans;

  return 0;
}

• 나중에 l < r은 제거했어도 되었는데, 이게 되는 이유는 이 성립함을 보이면 된다.
  • 만약 이 끝에 도달하지 않았는 데에도, collapse하려면 이어야 하는데 이 경우는 끝에 도달하는 경우밖에 없다.

BOJ 2470 : 두 용액 (Gold 5)

• 절댓값을 기준으로 정렬하고 윈도우 크기가 2인 슬라이딩 윈도우를 돌면 된다.
• 증명을 간단히 스케치해보자면...
  • 가 있을 때, 의 8개의 순서쌍을 고려해보자.¹
  • 이때, 인접한 나 가 아닌 가 최소가 될 경우가 있는지 살펴보자.
    1. :
    2. :
    3. :
    4. :
    5. :
    6. :
    7. :
    8. :
  • 모든 경우에 대해 성립하므로 절댓값을 기준으로 정렬된 3-튜플에 대해 인접한 값의 경우에만 고려해도 된다는 사실을 알게 되었다.
  • 이를 -튜플로 확장하여도 문제가 없다. 증명 끝.

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

using vi = vector<int>;
using pi = pair<int, int>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi arr(n);
  for (int i=0;i<n;i++)
    cin >> arr[i];

  sort(arr.begin(), arr.end(), [](int a, int b){
    return abs(a) < abs(b);
  });

  int mm = numeric_limits<int>::max();
  pi ans;
  for (int i=1;i<n;i++) {
    int cur = abs(arr[i-1] + arr[i]);
    if (mm > cur) {
      mm = cur;
      if (arr[i-1] > arr[i])
        ans = {arr[i], arr[i-1]};
      else
        ans = {arr[i-1], arr[i]};
    }
  }

  cout << ans.first << ' ' << ans.second;

  return 0;
}

BOJ 2467 : 용액 (Gold 5)

• BOJ 2470 코드로 해결 가능하다.

BOJ 1167 : 트리의 지름 (Gold 2)

• 트리 노드의 부모가 주어지는 게 아니라 Adjacency List가 주어져서 이번에는 BFS가 아니라 DFS만으로 해결해보았다.

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

using pi = pair<int, int>;

vector<vector<pi>> G;
bitset<100'001> visited;

pi dfs(int u) {
  if (visited[u]) return {0, -1};
  visited[u] = true;

  pi maxtwo{0, 0};
  int mm = 0;
  for (auto [v, w] : G[u]) {
    auto [a, b] = dfs(v);
    if (b == -1) continue;
    mm = max(mm, a);
    if (b+w > maxtwo.first) {
      maxtwo.second = maxtwo.first;
      maxtwo.first = b+w;
    } else if (b+w > maxtwo.second) {
      maxtwo.second = b+w;
    }
  }

  return {max(mm, maxtwo.first + maxtwo.second), maxtwo.first};
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int V; cin >> V; G.resize(V+1);
  for (int i=0;i<V;i++) {
    int u; cin >> u;
    int v; cin >> v;
    while (v != -1) {
      int w; cin >> w;
      G[u].emplace_back(v, w);
      cin >> v;
    }
  }

  cout << dfs(1).first;
  return 0;
}

BOJ 15681 : 트리와 쿼리 (Gold 5)

• DFS를 돌리면 된다.

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

vector<vector<int>> G;
bitset<100'001> visited;
vector<int> res;

int dfs(int u) {
  if (visited[u]) return 0;
  visited[u] = true;

  int cnt = 1;
  for (int v : G[u]) {
    cnt += dfs(v);
  }
  return res[u] = cnt;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, R, Q; cin >> N >> R >> Q;
  G.resize(N+1);
  res.resize(N+1);
  for (int i=0;i<N-1;i++) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  dfs(R);

  while (Q--) {
    int u; cin >> u;
    cout << res[u] << '\n';
  }

  return 0;
}

BOJ 2805 : 나무 자르기 (Silver 2)

• 이분 탐색 하면 된다.
• upper bound를 구하면 되는데, 부등호가 여전히 헷갈린다.

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

using vi = vector<int>;
using ll = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vi h(n);

  for (int i=0;i<n;i++)
    cin >> h[i];

  int lo = 0, hi = 1'000'000'001;
  while (lo < hi) {
    ll sum = 0;
    int mid = lo + (hi - lo) / 2;
    for (int i=0;i<n;i++)
      sum += max(h[i] - mid, 0);
    if (sum < m)
      hi = mid;
    else
      lo = mid + 1;
  }

  cout << (lo - 1);

  return 0;
}

BOJ 2239 : 스도쿠 (Gold 4)

• 백트래킹으로 풀면 된다.

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

int mat[81];

bool check(int i, int v) {
  int x = i / 9, y = i % 9;
  for (int j=0;j<9;j++) {
    int cellIdx = (x - x%3 + j/3)*9 + (y - y%3 + j%3);
    if (j != y && mat[x * 9 + j] == v ||
        j != x && mat[j * 9 + y] == v ||
        cellIdx != i && mat[cellIdx] == v) return false;
  }
  return true;
}

bool dfs(int i) {
  if (mat[i] > 0) return dfs(i+1);
  if (i == 81) return true;
  for (int v=1;v<=9;v++) {
    if (check(i, v)) {
      mat[i] = v;
      if (dfs(i + 1)) return true;
      mat[i] = 0;
    }
  }
  return false;
}

int main() {
  for (int i=0;i<9;i++)
    for (int j=0;j<9;j++)
      scanf("%1d", &mat[i*9+j]);

  dfs(0);

  for (int i=0;i<9;i++) {
    for (int j=0;j<9;j++)
      printf("%1d", mat[i*9+j]);
    printf("\n");
  }
  return 0;
}