BOJ problem - solution 정리 (

Jinhuyk Mun

Student. CSE

Daily Study Algorithm PS

BOJ problem - solution 정리 ( - 24.08)

Aug 31, 2023

2024년 8월까지 BOJ 문제풀이 통합 (24.09.01)

24.04.11 문제풀이

24.04.11

이 날부터 사지방 연등을 하면서 푸는 문제들을 요약하여 올릴려고함.

class 6 문제 위주로 풀었음.

boj 13907 - 세금

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

노드의 값이 바뀔때마다 최단경로를 구해야함
노드의 값이 바뀔때마다 dijkstra를 실행하면 TLE ( O(KN + KMlgM))
dist를 2차원 배열로 바꾸어 dist(최종노드, 거쳐온 노드) 로 저장

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
int N, M, K, S, D;
vector<ii> g[1010];
vector<vector<int>> dist(1010, vector<int>(1010, 1e9));

void dijkstra() {
  priority_queue<iii> pq;
  dist[S][0] = 0;
  pq.push({0, S, 0});

  while (!pq.empty()) {
    int cur, cnt, curw;

    tie(curw, cur, cnt) = pq.top();
    curw *= -1;
    pq.pop();
    if (cnt > N)
      continue;
    if (dist[cur][cnt++] < curw)
      continue;

    for (auto e : g[cur]) {
      int nxt = e.first;
      int nxtw = e.second;

      if (dist[nxt][cnt] > curw + nxtw) {
        dist[nxt][cnt] = curw + nxtw;
        pq.push({-dist[nxt][cnt], nxt, cnt});
      }
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> M >> K;
  cin >> S >> D;
  for (int i = 0; i < M; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    g[a].push_back({b, w});
    g[b].push_back({a, w});
  }

  dijkstra();
  int ans = 1e9;
  for (int i = 0; i <= N; i++) {
    ans = min(ans, dist[D][i]);
  }
  cout << ans << "\n";
  while(K--) {
    int p;
    cin >> p;
    ans = 1e9;
    for (int i = 0; i < N; i++) {
      ans = min(ans, dist[D][i] = dist[D][i] + i * p);
    }
    cout << ans << "\n";
  }
}

boj 1948 - 임계경로

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

DAG 에서 최장 경로를 찾은 후, 해당 경로에 있는 노드의 개수를 카운팅
dfs를 이용하여 역추적으로 노드의 개수 세기 가능

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vector<ii> g[10100], rg[10100];
vi ind(10100), d(10100);
vector<bool> vt(10100, false);
int cnt;
void f(int cur) {
  if (vt[cur])
    return;
  vt[cur] = true;
  for (auto x : rg[cur]) {
    int nxt = x.first;
    int w = x.second;
    if (d[cur] == d[nxt] + w) {
      f(nxt);
      cnt++;
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;

  while (m--) {
    int a, b, t;
    cin >> a >> b >> t;
    g[a].push_back({b, t});
    rg[b].push_back({a, t});
    ind[b]++;
  }
  int s, e;
  cin >> s >> e;
  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (ind[i] == 0)
      q.push(i);
  }
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto x : g[cur]) {
      int nxt = x.first;
      int w = x.second;
      if (d[nxt] < d[cur] + w) {
        d[nxt] = d[cur] + w;
      }
      if (--ind[nxt] == 0)
        q.push(nxt);
    }
  }
  f(e);
  int ans = 0;
  for (auto x : d)
    ans = max(ans, x);
  cout << ans << "\n" << cnt << "\n";
}

boj 1516 - 게임 개발

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

위상정렬 + DP
각 위상정렬마다의 최장 경로를 구해주면 됨

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vi g[505];
int ind[505], d[505], c[505];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
    while (true) {
      int b;
      cin >> b;
      if (b == -1)
        break;
      g[b].push_back(i);
      ind[i]++;
    }
  }
  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (ind[i] == 0) {
      q.push(i);
      d[i] = c[i];
    }
  }
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto x : g[cur]) {
      int nxt = x;
      d[nxt] = max(d[nxt], d[cur] + c[nxt]);
      if (--ind[nxt] == 0)
        q.push(nxt);
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << d[i] << endl;
  }
}

24.04.12-13 문제풀이

24.04.12 ~ 24.04.13

class 6 달성

고급 DP들과 기상한 풀이들을 공부하는것이 재밌어질 시기

BOJ 1471 - 사탕 돌리기

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

dfs를 이용하여 각 노드간 그래프를 만들어야함
사이클 내 노드의 개수를 카운트 후 sz[i] 에 저장해야함
각 자리수의 합을 찾는 기술 + 사이클의 노드 개수 카운팅

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int to[202020], sz[202020], N;
bool vt[202020];

int dfs(int u) {
  int &ret = sz[u];
  if (ret != -1)
    return ret;
  vt[u] = true;
  int v = u, t = u;
  while (t > 0) {
    v += t % 10;
    t /= 10;
  }
  if (v > N)
    v -= N;
  to[u] = v;

  if (vt[v]) {
    if (sz[v] != -1)
      return ret = sz[v] + 1;
    ret = 1;
    for (int r = v; r != u; r = to[r])
      ++ret;
    for (int r = v; r != u; r = to[r])
      sz[r] = ret;
    return ret;
  }
  dfs(v);
  if (ret == -1)
    return ret = dfs(v) + 1;
  return ret;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  memset(sz, -1, sizeof(sz));
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    ans = max(ans, dfs(i));
  }
  cout << ans << '\n';
}

BOJ 1509 - 팰린드롬 분할

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

p[i][j] : 문자열의 i~j 까지가 팰린드롬인지 나타내는 배열
d[i] : 1~ i 까지의 최소분할 개수
만약 j~i 가 팰린드롬인경우 d[i] = min(d[i] , d[j-1]+1)

위의 식이 성립하는 이유는 회문이 있는경우 분할 할 수 있는데, 이는 1~j-1 까지의 분할 개수와 j~i 의 회문 하나를 더한 것과 비교를 할 수 있다.

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
ll p[2525][2525], dp[2525];
int N;
string str;

int ispal(int i, int j) {
  ll &ret = p[i][j];
  if (ret != -1)
    return ret;
  if (i >= j)
    return 1;
  if (str[i] != str[j])
    return ret = 0;
  return ret = ispal(i + 1, j - 1);
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> str;
  N = str.size();
  str = ' ' + str;
  memset(p, -1, sizeof(p));

  dp[0] = 0;
  for (int i = 1; i <= N; i++) {
    dp[i] = 1e9;
    for (int j = 1; j <= i; j++) {
      if (ispal(j, i))dp[i] = min(dp[i], dp[j - 1] + 1);
    }
  }
  cout << dp[N] << '\n';
}

BOJ 1006 - 습격자 초라기

환형 타일링 DP 문제

생각해야하는 부분이 많았던 문제. dp[N][0] - N번째에서 위만 채우는 최소 개수 dp[N][1] - N번쨰에서 아래만 채우는 최소 개수 dp[N][2] - N번째 둘다 채우는 최소 개수

i=2 일때부터 dp[i][0], dp[i][1], dp[i][2]를 순서대로 채워준다. 이때 e[i][k] 의 값에 따라 2개 블럭을 묶는 경우와 묶지 않는 경우를 나눠서 계산해준다.
환형이기 때문에 1번째와 N번째의 관계에 따라 타일링을 다르게 해야한다. 각 경우에 따라 e[i][k]의 값을 무한으로 바꾸어 해당 칸에 대해서는 선택을 못하게끔 조정한다.

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
int dp[10101][3], e[10101][2], N, W;
void f() {
  for (int i = 2; i <= N; i++) {
    int p1 = (e[i - 1][0] + e[i][0] <= W) ? 1 : 2;
    int p2 = (e[i - 1][1] + e[i][1] <= W) ? 1 : 2;
    int p3 = (e[i][0] + e[i][1] <= W) ? 1 : 2;

    dp[i][0] = min(dp[i - 1][2] + 1, dp[i - 1][1] + p1);
    dp[i][1] = min(dp[i - 1][2] + 1, dp[i - 1][0] + p2);
    dp[i][2] = min({dp[i - 1][2] + p3, dp[i - 2][2] + p1 + p2, dp[i][0] + 1,
                    dp[i][1] + 1});
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int TC;
  cin >> TC;
  while (TC--) {

    cin >> N >> W;

    for (int i = 1; i <= N; i++)
      cin >> e[i][0];
    for (int i = 1; i <= N; i++)
      cin >> e[i][1];
    int ans = 1e9;

    
    int tmp1 = e[1][0];
    int tmp2 = e[1][1];
    dp[1][0] = dp[1][1] = 1;
    dp[1][2] = (e[1][0] + e[1][1] <= W) ? 1 : 2;
    f();
    ans = min(ans, dp[N][2]);

    memset(dp, 0, sizeof(dp));
    if (N != 1 && e[1][0] + e[N][0] <= W) {
      dp[1][0] = dp[1][1] = 1;
      dp[1][2] = 2;
      e[1][0] = 1e9;
      f();
      ans = min(ans, dp[N][1]);
      e[1][0] = tmp1;
      memset(dp, 0, sizeof(dp));
    }
    if (N != 1 && e[1][1] + e[N][1] <= W) {
      dp[1][0] = dp[1][1] = 1;
      dp[1][2] = 2;
      e[1][1] = 1e9;
      f();
      ans = min(ans, dp[N][0]);
      e[1][1] = tmp2;
      memset(dp, 0, sizeof(dp));
    }
    if (N != 1 && e[1][1] + e[N][1] <= W && e[1][0] + e[N][0] <= W) {
      dp[1][0] = dp[1][1] = 1;
      dp[1][2] = 2;
      e[1][0] = e[1][1] = 1e9;
      f();
      ans = min(ans, dp[N - 1][2]);
    }
    cout << ans << "\n";
  }
}

BOJ 13334 - 철로

priority_queue를 써서 풀어야하지만 집합을 이용한 기가막힌 풀이가 존재 해서 집합으로 풀이
$cnt(c) = [a_i , b_i] \subseteq [c, c+d]$ 의 개수를 만족해야 하는 cnt의 max를 찾으면 되는 문제
즉 위의 식은 다음처럼 바꿀 수 있음 $cnt(c) = {i | a_i >= c} \cap { i| b_i <= c +d}$

$cnt(c) = A \cap B$ 로 줄일 수 있다. 이제 이 식을 풀어서 다음처럼 만들 수 있다.

$A \cap B = n(A) + n(B) + n(A^c \cap B^c) - n(U)$

이때 $A^c \cap B^c$를 공집합으로 만들어준다면 A의 개수, B의 개수, 전체 개수만으로도 답을 구할 수 있음.

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, d;
  vi in, out;
  vector<ii> v;

  cin >> N;
  v.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> v[i].first >> v[i].second;
    if (v[i].first > v[i].second)
      swap(v[i].first, v[i].second);
  }
  cin >> d;

  for (int i = 0; i < N; i++) {
    if (v[i].second - v[i].first > d)
      continue;
    in.push_back(v[i].first);
    out.push_back(v[i].second);
  }
  sort(in.begin(), in.end());
  sort(out.begin(), out.end());

  int c = -1, ans = 0;
  for (int i = 0; i < in.size(); i++) {
    if (in[i] == c)
      continue;
    c = in[i];
    int t = in.end() - lower_bound(in.begin(), in.end(), c);
    t += upper_bound(out.begin(), out.end(), c + d) - out.begin();
    t -= in.size();
    ans = max(ans, t);
  }
  cout << ans << endl;
}

24.04.14 문제풀이

24.04.14

BOJ 1019 - 책페이지

1부터 N 까지 0~9 숫자가 몇번 나오는지 카운트하는 문제
기본적인 탐색으로는 $O(N)$ 으로 TLE
x0 ~y9 까지는 0부터 9가 (y-x+1) 번씩 나온다는 것을 이용
만약 xk 인 경우 x’0 으로 만들어 주기 위해 하나씩 더해가면서 해당 숫자의 자리에 0~9 까지를 카운트
yt 에서 y’9로 가는 것도 동일하게 카운트
x0 ~y9 까지 계산 완료시, x ~ y를 똑같이 반복하여 계산

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

ll ans[10];

void f(ll n, ll t) {
  while (n > 0) {
    ans[n % 10] += t;
    n /= 10;
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  ll s = 1, e, t = 1;

  cin >> e;

  while (s <= e) {
    while (s % 10 != 0 && s <= e) {
      f(s, t);
      s++;
    }
    if (s > e)
      break;
    while (e % 10 != 9 && s <= e) {
      f(e, t);
      e--;
    }
    ll cnt = (e / 10 - s / 10 + 1);
    for (int i = 0; i <= 9; i++) {
      ans[i] += cnt * t;
    }
    s /= 10;
    e /= 10;
    t *= 10LL;
  }
  for (int i = 0; i <= 9; i++) {
    cout << ans[i] << ' ';
  }
}

BOJ 2482 - 색상환

환형 + 경우의수 + DP
D(i,j) = i번째에서 j개를 뽑는 경우의 수
$D(i,j) = D(i-2,j-1) + d(i-1,j)$ i번째를 사용하는 경우에는 i-1은 사용할 수 없으므로 (i-2, j-1)을 사용 i번째를 사용하지 않는 경우엔 (i-1,j)를 사용하면 됨.
환형이기 때문에 N번째인경우 고려를 해줘야함
환형 DP에서는 N-1까지는 선형으로 생각하고, N번째에서 N-1과 1번째를 고려해주면 편함

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

const ll mod = 1e9 + 3;
ll D[1010][1010];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K;

  cin >> N >> K;
  for (int i = 1; i < 1001; i++) {
    D[i][0] = 1;
    D[i][1] = i;
  }

  for (int i = 2; i < N; i++) {
    for (int j = 2; j <= i; j++) {
      D[i][j] = (D[i - 2][j - 1] + D[i - 1][j]) % mod;
    }
  }
  cout << ((D[N - 3][K - 1] + D[N - 1][K]) % mod) << "\n";
}

BOJ 17626 - Four Squares

기초 DP 문제

#define GG return 0
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
int D[50505], N;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> N;
  D[1] = 1;
  for (int i = 2; i <= N; i++) {
     int ret = 1e9;
     for(int j = 1; j*j <=i;j++){
         ret = min(ret, D[i-j*j]);
     }
     D[i] = ret +1;
  }
  cout << D[N] << "\n";
}

24.04.15 문제풀이

24.04.15

BOJ 3176 - 도로 네트워크

sparse table + LCA
노드에 대한 sparse table과 min, max의 정보가 담긴 sparse table 생성해야함
두 노드의 lca를 구하고 각 노드와 lca 사이에서 min, max를 찾아야함

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vector<ii> g[101010];
int depth[101010], st[101010][20],mx[101010][20], mn[101010][20], N;
int k, da, db;
bool vt[101010];
void dfs(int u,int d){
    vt[u] = true;
    depth[u] = d;
    for(auto v : g[u]){
        if(vt[v.first]) continue;
        st[v.first][0] = u;
        mx[v.first][0] = mn[v.first][0] = v.second;
        dfs(v.first,d+1);
    }
}

void table(){
    for(int j = 1; j<20;j++){
        for(int i = 1; i<=N;i++){
            st[i][j] = st[st[i][j-1]][j-1];
            mn[i][j] = min(mn[i][j-1], mn[st[i][j-1]][j-1]);
            mx[i][j] = max(mx[i][j-1], mx[st[i][j-1]][j-1]);
        }
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u,v);
    int dif = depth[u] - depth[v];
    for(int i = 0; dif; i++){
        if(dif & 1) {
            u = st[u][i];
            
        }
        dif >>=1;
    }
    if(u == v) return u;
    for(int i = 19;i>=0;i--){
        if(st[u][i] != st[v][i]){
            u = st[u][i], v= st[v][i];
            
        }
    }
    return st[u][0];
}


int main(void){
    ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> N;
  for(int i = 0; i<N-1;i++){
      int a,b,c; cin >> a >> b >>c;
      g[a].push_back({b,c});
      g[b].push_back({a,c});
  }

  dfs(1,0);
  table();
  
  int m ; cin >> m;
  while(m--){
      int a,b; cin >> a >> b;
      k = lca(a,b);
      da = depth[a] - depth[k], db = depth[b] - depth[k];
      int retmx =-1, retmn = 1e9;
      
      for(int i = 19; i>= 0;i--){
          if(da >= (1<< i)){
              retmx = max(retmx, mx[a][i]);
              retmn = min(retmn, mn[a][i]);
              da -=(1 << i);
              a = st[a][i];
          }
      }
      for(int i = 19; i>= 0;i--){
          if(db >= (1<< i)){
              retmx = max(retmx, mx[b][i]);
              retmn = min(retmn, mn[b][i]);
              db -=(1 << i);
              b = st[b][i];
          }
      }
      cout << retmn <<" " << retmx <<"\n";
  }
}

BOJ 3584 - 가장 가까운 공통 조상

tree root를 찾아서 dfs를 돌린 뒤 lca 적용
parent 정보만 있는 tree에서 root를 찾고, depth를 만드는 방법이 나와있음

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector < int >vi;
typedef pair < int, int >ii;
typedef tuple < int, int, int >iii;

vi g[101010];
int depth[101010], st[101010][20], N;
bool vt[101010];
void dfs (int u)
{
    for(int v : g[u]){
        if(depth[v] == -1){
                    depth[v] = depth[u] +1;
        st[v][0] =u;
        dfs(v);
        }

    }
}

void table ()
{
  for (int j = 1; j < 20; j++)
	{
	  for (int i = 1; i <= N; i++)
		{
		  st[i][j] = st[st[i][j - 1]][j - 1];
		}
	}
}

int lca (int u, int v)
{
  if (depth[u] < depth[v])
	swap (u, v);
  int dif = depth[u] - depth[v];
  for (int i = 0; dif; i++)
	{
	  if (dif & 1)
		{
		  u = st[u][i];

		}
	  dif >>= 1;
	}
  if (u == v)
	return u;
  for (int i = 19; i >= 0; i--)
	{
	  if (st[u][i] != st[v][i])
		{
		  u = st[u][i], v = st[v][i];

		}
	}
  return st[u][0];
}


int main (void)
{
  ios::sync_with_stdio (0);
  cin.tie (0);
  int TC;
  cin >> TC;
  while (TC--)
	{
	  memset (st, 0, sizeof (st));
	  memset (depth, 0, sizeof (depth));
	  memset (vt, false, sizeof (vt));
	  for (int i = 0; i < 101010; i++)
		{
		  g[i].clear ();
		}
	  cin >> N;
	  for (int i = 0; i < N - 1; i++)
		{
		  int a, b;
		  cin >> a >> b;
		  g[a].push_back (b);
		  ++depth[b];
		}
	   int r;
	   for(int i = 1; i<=N;i++){
	       if(depth[i] == 0){
	         r = i;  
	       }
	   }
	   memset(depth, -1, sizeof(depth));
	   depth[r] = 0;
	  dfs (r);
	  table ();

	  int a, b;
	  cin >> a >> b;
	  cout << lca (a, b) << "\n";

	}



}

노드가 N개인 K진 트리 생성

for (int i = 1, k = 2;; i++)
	{
	  int z = K;
	  for (; z > 0; k++, z--)
		{


		  g[i].push_back (k);
		  if (k == N)
			return;
		}
	}

24.04.16

Tarjan’s Algorithm

SCC를 찾는 알고리즘으로 $O(V+E)$에 시간복잡도를 가지고 있다. dfs Tree에서

order[i] : i번째 정점이 몇번째 방문인지,

low[i] : i번 정점을 루트로 하는 서브 트리에서 간선하나로 갈수 있는 정점중 가장 작은 low값을 의미함.

BOJ 11266 - 단절점

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

Tarjan’s Algorithm을 이용하여 단절점을 구할 수 있음
단절점의 조건은 다음과 같음
1. V가 단절점이 아님 –> V의 자손 중 V를 거치지 않고 한번에 V위의 정점(방문정점) 을 갈 수 있음
2. V가 root 라면 자식이 2개 이상인 경우 단절점

이 조건을 이용하여 Naive 방식을 제외한 Tarjan’s Algorihtm을 이용하여 코드 작성

제시되는것이 하나의 컴포넌트 그래프가 아닐 수 있으므로, vt[i]를 사용하여 컴포넌트 그래프마다 확인해야함

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vi g[10101];
int order[10101], low[10101],t;
bool vt[10101];
set<int> ans;

void dfs(int u, int par){
    order[u] = t++;
    low[u] = t;
    vt[u] = true;
    int sub = 0;
    for(auto v : g[u]){
        if(!vt[v]){
            sub++;
            dfs(v,u);
            low[u] = min(low[u],low[v]);
            if(par != -1 && low[v] >= order[u]) ans.insert(u);
        }
        else if(v != par) low[u] = min(low[u], order[v]);
    }
    if(par == -1 && sub > 1) ans.insert(u);
}

int main(void){
    FASTIO;
    int V,E;
    cin >> V >> E;
    while(E--){
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    for(int i = 1; i<=V;i++){
        if(!vt[i]) dfs(i,-1);
    }
    cout << ans.size() <<"\n";
    for(auto i : ans) cout << i <<" ";
}

BOJ 11400 - 단절선

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

tarjan’s algorithm을 이용하여 구현
다음 조건을 만족 시 단절선
1. 현재 정점 A와 자식 정점B를 잇는 간선에서A의 자손들 중 A를 거치지 않고, A 이전 방문 정점에갈수 없는 경우

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vi g[101010];
int order[101010], low[101010],t;
bool vt[101010];
vector<ii> ans;

void dfs(int u, int par){
    order[u] = t++;
    low[u] = t;
    for(auto v : g[u]){
        if(v == par) continue;
        if(order[v] == 0){
            dfs(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > order[u]) ans.push_back({min(u,v), max(u,v)});
        }
        else low[u] = min(low[u], order[v]);
    }
}

int main(void){
    FASTIO;
    int V,E;
    cin >> V >> E;
    while(E--){
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    dfs(1,-1);
    cout << ans.size() <<"\n";
    sort(ans.begin(), ans.end());
    for(auto i : ans) cout << i.first <<" " <<i.second<<"\n";
}

BOJ 11308 - One-Way Road

단절선을 찾는 문제
역으로, 단절선이 있지 않은 경우 이어지는 모든 간선을 찾으면 됨

중복되는 간선이 있을 수 있으므로, 간선 처리 시 g[x][y]로 사용하였음

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int g[55][55];
int order[55], low[55],t;
vi ans[55];
int V,E;
bool dfs(int u, int par){
    bool res = 0;
    order[u] = low[u] = ++t;
    for(int v = 1; v<=V;v++) if(g[u][v]){
        g[u][v]--;
        g[v][u]--;
        if(v == par) continue;
        ans[v].push_back(u);
        if(order[v] == 0){
            res |= dfs(v,u);
            low[u] = min(low[u],low[v]);
        }
        else low[u] = min(low[u], order[v]);
        if(order[u] < low[v]) res = 1;
    }
    return res;
}

int main(void){
    FASTIO;
    int TC; cin >>TC;
    while(TC--){
        for(int i = 0;i<55;i++) {ans[i].clear();}
        memset(order,0,sizeof(order));
        memset(low,0,sizeof(low));
        memset(g,0,sizeof(g));
        t = 0;
        
        cin >> V >> E;
        while(E--){
            int u,v; cin >> u >> v;
            g[v][u]++;
            g[u][v]++;
        }
        
        bool f = dfs(1,-1);
        if(f) cout << "NO"<<"\n";
        else{
            cout << "YES\n";
            for(int i = 1; i<=V;i++){
                
                for(auto j : ans[i]){
                    cout << i <<" " <<j <<"\n";
                }
            }
        }

    }
    
}

24.04.16 문제풀이

24.04.17

인접행렬의 거듭제곱

0과 1로 이루어진 인접행렬에 대해서 i->j 를 1로 생각하는경우, 해당 인접행렬의 N제곱은 i에서 N번 이동했을때 j로 가는 경우의 수를 의미함.

BOJ 1533 - 길의 개수

인접행렬의 거듭제곱
해당 행렬은 binary matrix가 아니기 때문에 인접행렬의 거듭제곱 기법을 사용할 수 없음 –> 정점을 분할하여 binary matrix로 만들어 사용
해당 행렬을 5배로 늘려, i5+0, i5+1 … , i*5+4 에 각각 v0, v1,, v4 를 할당시켜줌
v4-> v3 을 1의 가중치를 넣어줌 (다른 vVn -> Vn-1 도 동일하게)

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

#define x first
#define y second
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const ll mod = 1000003;
struct Matrix{
	int size;
	vector< vector<ll> > arr;
	Matrix(){size = 0;}
	Matrix(int n){
		size = n;
		arr = vector< vector<ll> >(n, vector<ll>(n));
	}
	Matrix operator * (const Matrix &x){
		Matrix ret(size);
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					ret.arr[i][j] += arr[i][k] * x.arr[k][j];
					ret.arr[i][j] %= mod;
				}
			}
		}
		return ret;
	}
};

Matrix powmat(Matrix a, ll b){
	if(b == 1) return a;
	Matrix ret = powmat(a, b/2);
	ret = ret * ret;
	if(b & 1) ret = ret * a;
	return ret;
}


int main(void){
    FASTIO
    int N,S,E,T; cin>> N >> S >> E >>T;
    
    S--; E--;
    
    Matrix mat(N*5);
    
    for(int i = 0;i<N;i++){
        for(int j = 1; j<5;j++){
            mat.arr[i*5+j][i*5+j-1] = 1;
        }
    }
    
    for(int i = 0;i<N;i++){
        string str; cin >> str;
        
        for(int j = 0;j<N;j++){
            int t = str[j] - '0';
            if(t == 1) mat.arr[i*5][j*5] = 1;
            else if(t > 1) mat.arr[i*5][j*5+t-1] =1;
        }
    }
    
    Matrix ans = powmat(mat,T);
    cout << ans.arr[S*5][E*5];
}

BOJ 12850 - 본대산책2

인접행렬을 이용한 거듭제곱을 이용한 문제

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

#define x first
#define y second
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const ll mod = 1000000007;
struct Matrix{
	int size;
	vector< vector<ll> > arr;
	Matrix(){size = 0;}
	Matrix(int n){
		size = n;
		arr = vector< vector<ll> >(n, vector<ll>(n));
	}
	Matrix operator * (const Matrix &x){
		Matrix ret(size);
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					ret.arr[i][j] += arr[i][k] * x.arr[k][j];
					ret.arr[i][j] %= mod;
				}
			}
		}
		return ret;
	}
};

Matrix powmat(Matrix a, ll b){
	if(b == 1) return a;
	Matrix ret = powmat(a, b/2);
	ret = ret * ret;
	if(b & 1) ret = ret * a;
	return ret;
}


int main(void){
    FASTIO
    int D; cin>> D;
    Matrix mat(8);
    mat.arr = {
        {0, 1, 1, 0, 0, 0, 0, 0},
        {1, 0, 1, 1, 0, 0, 0, 0},
        {1, 1, 0, 1, 1, 0, 0, 0},
        {0, 1, 1, 0, 1, 1, 0, 0},
        {0, 0, 1, 1, 0, 1, 0, 1},
        {0, 0, 0, 1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 1, 0, 1},
        {0, 0, 0, 0, 1, 0, 1, 0}
};
    
    Matrix ans = powmat(mat,D);
    cout << ans.arr[0][0];
}

BOJ 14289 - 본대산책3

인접행렬을 이용한 거듭제곱 문제
본대산책 2와 동일

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

#define x first
#define y second
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const ll mod = 1000000007;
struct Matrix{
	int size;
	vector< vector<ll> > arr;
	Matrix(){size = 0;}
	Matrix(int n){
		size = n;
		arr = vector< vector<ll> >(n, vector<ll>(n));
	}
	Matrix operator * (const Matrix &x){
		Matrix ret(size);
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					ret.arr[i][j] += arr[i][k] * x.arr[k][j];
					ret.arr[i][j] %= mod;
				}
			}
		}
		return ret;
	}
};

Matrix powmat(Matrix a, ll b){
	if(b == 1) return a;
	Matrix ret = powmat(a, b/2);
	ret = ret * ret;
	if(b & 1) ret = ret * a;
	return ret;
}


int main(void){
    FASTIO
    int n,m,D; cin>>n >> m;
    Matrix mat(n);
    for(int i = 0;i<m;i++){
        int a,b; cin >> a >> b;
        a--,b--;
        mat.arr[a][b] =mat.arr[b][a] = 1;
    }
    cin >> D;
    Matrix ans = powmat(mat,D);
    cout << ans.arr[0][0];
}

24.04.20 문제풀이

24.04.20

2일동안 사지방 연등을 신청하지 못해서 아쉽게도 일지를 못올렸었다.

2-SAT 문제

$ L = (a_1 \vee b_1 ) \wedge (a_2 \vee b_2 ) \wedge (a_3 \vee b_3 ) \wedge … (a_m \vee b_m ) \wedge $

$L$ 이 참이거나 그런 조합이 없음을 나타내어야함

implication graph를 이용하여 SCC를 구한 후 $x_i$과 $ \neg x_i$ 이 모두 같은 scc에 속해있지 않으면 됨
implication graph
- 노드 : $x_i$ , $ \neg x_i $
- 간선 : 변수간 관계 -> $(x_i \vee y_i)$ 는 $\neg x_i \rightarrow y_i$ 와 $\neg y_i \rightarrow x_i$
2-SAT 문제를 많이 접해보기 위해 kks227 님의 문제 목록을 기준으로 풀것임. https://m.blog.naver.com/kks227/220803009418
담주부터 바빠져서 작성이 늦어질수도.
BOJ 11280 - 2-SAT 3
2-sat 기본 문제

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

vector<int> g[20202], rev[20202],vv;

bool vt[20202];
int scc[20202];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<=n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    
    for(int i = 0;i<m;i++){
        int a,b; cin >> a >> b;
        if(a > 0) a = trueX(a);
        else a = falseX(-a);
        if(b>0) b = trueX(b);
        else b = falseX(-b);
        g[notX(a)].push_back(b);
        g[notX(b)].push_back(a);
        rev[b].push_back(notX(a));
        rev[a].push_back(notX(b));
    }
    
    getscc(n);
    
    for(int i = 1; i<=n;i++){
        if(scc[trueX(i)] == scc[falseX(i)]){
            cout << "0"; return 0;
        }
    }
    cout << 1 <<"\n";
}

BOJ 3747 - 완벽한 선거!

while(cin » n » m) 으로 eof 를 정해주면 되는 문제

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

vector<int> g[20202], rev[20202],vv;

bool vt[20202];
int scc[20202];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<=n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; 
    
    while(cin >> n >> m){
        for(int i = 0; i <=4*n;i++){
            g[i].clear();
            rev[i].clear();
        }
        vv.clear();
        memset(scc,0,sizeof scc);
        
        for(int i = 0;i<m;i++){
            int a,b; cin >> a >> b;
            if(a > 0) a = trueX(a);
            else a = falseX(-a);
            if(b>0) b = trueX(b);
            else b = falseX(-b);
            g[notX(a)].push_back(b);
            g[notX(b)].push_back(a);
            rev[b].push_back(notX(a));
            rev[a].push_back(notX(b));
        }
        
        getscc(n);
        bool flag = false;
        for(int i = 1; i<=n;i++){
            if(scc[trueX(i)] == scc[falseX(i)]){
                flag = true; break;
            }
        }
        cout << (flag ? 0 : 1) <<"\n";
    }
}

BOJ 2207 - 가위바위보

위의 문제와 똑같은 문제
n과m의 자리를 바꾸면 됨

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

vector<int> g[20202], rev[20202],vv;

bool vt[20202];
int scc[20202];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<=n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> m >> n;
    
    for(int i = 0;i<m;i++){
        int a,b; cin >> a >> b;
        if(a > 0) a = trueX(a);
        else a = falseX(-a);
        if(b>0) b = trueX(b);
        else b = falseX(-b);
        g[notX(a)].push_back(b);
        g[notX(b)].push_back(a);
        rev[b].push_back(notX(a));
        rev[a].push_back(notX(b));
    }
    
    getscc(n);
    
    for(int i = 1; i<=n;i++){
        if(scc[trueX(i)] == scc[falseX(i)]){
            cout << "OTL"; return 0;
        }
    }
    cout << "^_^" <<"\n";
}

BOJ 2519 - 막대기

2-SAT 응용 + 선분교차
첫 다이아몬드 문제
https://justicehui.github.io/koi/2019/05/21/BOJ2519/ 를 참고
i 번쨰 사람은 3i , 3i+1, 3i+2 막대기를 가지고, 그중 하나를 제거할수 있으므로,

3i - $\neg$3i+1 , 3i - $\neg$3i+12 3i+1 - $\neg$3i, 3i+1 - $\neg$3i+1 3i+2 - $\neg$3i, 3i+2 - $\neg$3i+1

다음처럼 함의그래프를 이어준다.

또한 막대기의 교차또한 안되므로, x,y가 교차하는 경우에 $\neg$x -> y , $\neg$ y -> x 를 넣어준다.

scc를 돌리고 여부와, 참인 경우에 제거 막대기를 출력한다.

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



vector<int> g[20202], rev[20202],vv;
int X1[3030], Y1[3030],X2[3030],Y2[3030];
bool vt[20202];
int scc[20202];
int n;
inline int inv(int x){
	if(x >= 3*n) return x - 3*n;
	else return x + 3*n;
}

int ccw(int a, int b, int c, int d, int e, int f){
	int res = (c-a)*(f-b) - (d-b)*(e-a);
	return res > 0 ? 1 : -1;
}

bool cross(int i, int j){
	int t1 = ccw(X1[i], Y1[i], X2[i], Y2[i], X1[j], Y1[j]) * ccw(X1[i], Y1[i], X2[i], Y2[i], X2[j], Y2[j]);
	int t2 = ccw(X1[j], Y1[j], X2[j], Y2[j], X1[i], Y1[i]) * ccw(X1[j], Y1[j], X2[j], Y2[j], X2[i], Y2[i]);
	return t1 < 0 && t2 < 0;
}


void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    scc[u] = c;
    for(auto v : rev[u]) if(!scc[v]) revdfs(v,c);
}

void getscc(){
    for(int i = 0; i<n*6;i++){
        if(!vt[i]) dfs(i);
    }
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!scc[i]) revdfs(i,cnt++);
        
    }
}
void add(int a, int b){
	g[a].push_back(b);
	rev[b].push_back(a);
	g[inv(b)].push_back(inv(a));
	rev[inv(a)].push_back(inv(b));
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    
    for(int i = 0; i<3*n;i++){
        cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
    }
    for(int i = 0;i<n;i++){
        add(3*i, inv(3*i+1));
        add(3*i, inv(3*i+2));
        add(3*i+1, inv(3*i));
        add(3*i+1, inv(3*i+2));
        add(3*i+2, inv(3*i));
        add(3*i+2, inv(3*i+1));
        
    }
    for(int i = 0;i<3*n;i++){
        for(int j = i+1; j<3*n;j++){
            if(cross(i,j)) add(inv(i),j);
        }
    }
    getscc();
    vector<int> ans;
	for(int i=0; i<3*n; i++){
		if(scc[i] == scc[inv(i)]){
			cout << -1; return 0;
		}
		if(scc[i] > scc[inv(i)]) ans.push_back(i+1);
	}
	cout << ans.size() << "\n";
	for(auto i : ans) cout << i << " ";
}

24.04.21 문제풀이

24.04.21

4월 21일도 2-sat 문제에 대해 적응하는 시간을 가졌다.

BOJ 7535 - A Bug’s Life

kks227님의 문제 리스트중 하나
2-sat으로 구할수 있음.
문자열 출력에서 빙빙 돌았던 문제

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

vector<int> g[4040], rev[4040],vv;

bool vt[4040];
int scc[4040];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, T;
    cin >> T;
    for(int t = 1; t<=T;t++){
        cin >> n >> m;
        for(int i = 0; i <4040;i++){
            g[i].clear();
            rev[i].clear();
        }
        vv.clear();
        memset(scc,0,sizeof scc);
        
        for(int i = 0;i<m;i++){
            int a,b; cin >> a >> b;
            if(a > 0) a = trueX(a);
            else a = falseX(-a);
            if(b>0) b = trueX(b);
            else b = falseX(-b);
            g[notX(a)].push_back(b);
            g[a].push_back(notX(b));
            g[notX(b)].push_back(a);
            g[b].push_back(notX(a));
            rev[b].push_back(notX(a));
            rev[a].push_back(notX(b));
            rev[notX(a)].push_back(b);
            rev[notX(b)].push_back(a);
        }

        getscc(n);
        bool flag = true;
        for(int i = 1; i<=n;i++){
            if(scc[trueX(i)] == scc[falseX(i)]){
                flag = false;
                break;
            }
        } 
        cout << "Scenario #"<<t<<":\n";
        cout << (flag ? "No s" : "S") << "uspicious bugs found!\n\n";
    }
}

BOJ 3648 - 아이돌

2-sat 문제
$x_1 \vee x_1$ 이어야 하므로 해당 식을 g에 넣어준 후 구현

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

vector<int> g[2020], rev[2020],vv;

bool vt[2020];
int scc[2020];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; 
    while(cin >> n >> m){
        for(int i = 0; i <2020;i++){
            g[i].clear();
            rev[i].clear();
        }
        vv.clear();
        memset(scc,0,sizeof scc);
        
        for(int i = 0;i<m;i++){
            int a,b; cin >> a >> b;
            if(a > 0) a = trueX(a);
            else a = falseX(-a);
            if(b>0) b = trueX(b);
            else b = falseX(-b);
            g[notX(a)].push_back(b);
            g[notX(b)].push_back(a);
            rev[b].push_ba24.04.20 문제풀이

### 24.04.20

2일동안 사지방 연등을 신청하지 못해서 아쉽게도 일지를 못올렸었다.

#### 2-SAT 문제
$ L = (a_1 \vee b_1 ) \wedge (a_2 \vee b_2 ) \wedge (a_3 \vee b_3 ) \wedge ... (a_m \vee b_m ) \wedge $

$L$ 이 참이거나 그런 조합이 없음을 나타내어야함

- implication graph를 이용하여 SCC를 구한 후 $x_i$과 $ \neg x_i$ 이 모두 같은 scc에 속해있지 않으면 됨

- implication graph
	- 노드 : $x_i$ , $ \neg x_i $
	- 간선 : 변수간 관계 -> $(x_i \vee y_i)$ 는 $\neg x_i \rightarrow y_i$ 와 $\neg y_i \rightarrow x_i$

- 2-SAT 문제를 많이 접해보기 위해 kks227 님의 문제 목록을 기준으로 풀것임.
https://m.blog.naver.com/kks227/220803009418

- 담주부터 바빠져서  작성이 늦어질수도.
#### BOJ 11280 - 2-SAT 3

- 2-sat 기본 문제

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

vector g[20202], rev[20202],vv;

bool vt[20202]; int scc[20202]; inline int notX(int x){ return x ^ 1; } inline int trueX(int x){ return x « 1; } inline int falseX(int x){ return x « 1 | 1; } void dfs(int u){ vt[u] = true; for(auto v : g[u]) if(!vt[v]) dfs(v); vv.push_back(u); }

void revdfs(int u, int c){ vt[u] = 1; scc[u] = c; for(auto v : rev[u]) if(!vt[v]) revdfs(v,c); }

void getscc(int n){ memset(vt,false,sizeof(vt)); for(int i = 2; i<=n*2 +1;i++){ if(!vt[i]) dfs(i); } memset(vt, false, sizeof vt); reverse(vv.begin(), vv.end()); int cnt = 1; for(auto i : vv){ if(!vt[i]) {revdfs(i,cnt); cnt++;}

} }

int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin » n » m;

for(int i = 0;i<m;i++){
    int a,b; cin >> a >> b;
    if(a > 0) a = trueX(a);
    else a = falseX(-a);
    if(b>0) b = trueX(b);
    else b = falseX(-b);
    g[notX(a)].push_back(b);
    g[notX(b)].push_back(a);
    rev[b].push_back(notX(a));
    rev[a].push_back(notX(b));
}

getscc(n);

for(int i = 1; i<=n;i++){
    if(scc[trueX(i)] == scc[falseX(i)]){
        cout << "0"; return 0;
    }
}
cout << 1 <<"\n"; } ```

BOJ 3747 - 완벽한 선거!

while(cin » n » m) 으로 eof 를 정해주면 되는 문제

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

vector<int> g[20202], rev[20202],vv;

bool vt[20202];
int scc[20202];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<=n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; 
    
    while(cin >> n >> m){
        for(int i = 0; i <=4*n;i++){
            g[i].clear();
            rev[i].clear();
        }
        vv.clear();
        memset(scc,0,sizeof scc);
        
        for(int i = 0;i<m;i++){
            int a,b; cin >> a >> b;
            if(a > 0) a = trueX(a);
            else a = falseX(-a);
            if(b>0) b = trueX(b);
            else b = falseX(-b);
            g[notX(a)].push_back(b);
            g[notX(b)].push_back(a);
            rev[b].push_back(notX(a));
            rev[a].push_back(notX(b));
        }
        
        getscc(n);
        bool flag = false;
        for(int i = 1; i<=n;i++){
            if(scc[trueX(i)] == scc[falseX(i)]){
                flag = true; break;
            }
        }
        cout << (flag ? 0 : 1) <<"\n";
    }
}

BOJ 2207 - 가위바위보

위의 문제와 똑같은 문제
n과m의 자리를 바꾸면 됨

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

vector<int> g[20202], rev[20202],vv;

bool vt[20202];
int scc[20202];
inline int notX(int x){ return x ^ 1; }
inline int trueX(int x){ return x << 1; }
inline int falseX(int x){ return x << 1 | 1; }
void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    vt[u] = 1;
    scc[u] = c;
    for(auto v : rev[u]) if(!vt[v]) revdfs(v,c);
}

void getscc(int n){
    memset(vt,false,sizeof(vt));
    for(int i = 2; i<=n*2 +1;i++){
        if(!vt[i]) dfs(i);
    }
    memset(vt, false, sizeof vt);
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!vt[i]) {revdfs(i,cnt); cnt++;}
        
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> m >> n;
    
    for(int i = 0;i<m;i++){
        int a,b; cin >> a >> b;
        if(a > 0) a = trueX(a);
        else a = falseX(-a);
        if(b>0) b = trueX(b);
        else b = falseX(-b);
        g[notX(a)].push_back(b);
        g[notX(b)].push_back(a);
        rev[b].push_back(notX(a));
        rev[a].push_back(notX(b));
    }
    
    getscc(n);
    
    for(int i = 1; i<=n;i++){
        if(scc[trueX(i)] == scc[falseX(i)]){
            cout << "OTL"; return 0;
        }
    }
    cout << "^_^" <<"\n";
}

BOJ 2519 - 막대기

2-SAT 응용 + 선분교차
첫 다이아몬드 문제
https://justicehui.github.io/koi/2019/05/21/BOJ2519/ 를 참고
i 번쨰 사람은 3i , 3i+1, 3i+2 막대기를 가지고, 그중 하나를 제거할수 있으므로,

3i - $\neg$3i+1 , 3i - $\neg$3i+12 3i+1 - $\neg$3i, 3i+1 - $\neg$3i+1 3i+2 - $\neg$3i, 3i+2 - $\neg$3i+1

다음처럼 함의그래프를 이어준다.

또한 막대기의 교차또한 안되므로, x,y가 교차하는 경우에 $\neg$x -> y , $\neg$ y -> x 를 넣어준다.

scc를 돌리고 여부와, 참인 경우에 제거 막대기를 출력한다.

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



vector<int> g[20202], rev[20202],vv;
int X1[3030], Y1[3030],X2[3030],Y2[3030];
bool vt[20202];
int scc[20202];
int n;
inline int inv(int x){
	if(x >= 3*n) return x - 3*n;
	else return x + 3*n;
}

int ccw(int a, int b, int c, int d, int e, int f){
	int res = (c-a)*(f-b) - (d-b)*(e-a);
	return res > 0 ? 1 : -1;
}

bool cross(int i, int j){
	int t1 = ccw(X1[i], Y1[i], X2[i], Y2[i], X1[j], Y1[j]) * ccw(X1[i], Y1[i], X2[i], Y2[i], X2[j], Y2[j]);
	int t2 = ccw(X1[j], Y1[j], X2[j], Y2[j], X1[i], Y1[i]) * ccw(X1[j], Y1[j], X2[j], Y2[j], X2[i], Y2[i]);
	return t1 < 0 && t2 < 0;
}


void dfs(int u){
    vt[u] = true;
    for(auto v : g[u]) if(!vt[v]) dfs(v);
    vv.push_back(u);
}

void revdfs(int u, int c){
    scc[u] = c;
    for(auto v : rev[u]) if(!scc[v]) revdfs(v,c);
}

void getscc(){
    for(int i = 0; i<n*6;i++){
        if(!vt[i]) dfs(i);
    }
    reverse(vv.begin(), vv.end());
    int cnt = 1;
    for(auto i : vv){
        if(!scc[i]) revdfs(i,cnt++);
        
    }
}
void add(int a, int b){
	g[a].push_back(b);
	rev[b].push_back(a);
	g[inv(b)].push_back(inv(a));
	rev[inv(a)].push_back(inv(b));
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    
    for(int i = 0; i<3*n;i++){
        cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
    }
    for(int i = 0;i<n;i++){
        add(3*i, inv(3*i+1));
        add(3*i, inv(3*i+2));
        add(3*i+1, inv(3*i));
        add(3*i+1, inv(3*i+2));
        add(3*i+2, inv(3*i));
        add(3*i+2, inv(3*i+1));
        
    }
    for(int i = 0;i<3*n;i++){
        for(int j = i+1; j<3*n;j++){
            if(cross(i,j)) add(inv(i),j);
        }
    }
    getscc();
    vector<int> ans;
	for(int i=0; i<3*n; i++){
		if(scc[i] == scc[inv(i)]){
			cout << -1; return 0;
		}
		if(scc[i] > scc[inv(i)]) ans.push_back(i+1);
	}
	cout << ans.size() << "\n";
	for(auto i : ans) cout << i << " ";
}

ck(notX(a)); rev[a].push_back(notX(b)); } int o = trueX(1); g[notX(o)].push_back(o); rev[o].push_back(notX(o)); getscc(n); bool flag = true; for(int i = 1; i<=n;i++){ if(scc[trueX(i)] == scc[falseX(i)]){ cout « “no\n”; flag = false; break; } } if(flag) cout « “yes\n”; } }

24.04.22 문제풀이

### 24.04.22

인접행렬 거듭제곱 문제풀이.

2-SAT 4 문제풀이 해야함 --> code 정비

#### BOJ 17401 - 일하는 세포

- 인접행렬의 거듭제곱 이용
- $ ABCABC \neq A^2 B^2 C^2 $ .. 즉 행렬의 교환법칙 성립은 안됨
- $ (ABC)^{D/T} * AB .. $ 이런식으로 계산해야함

- D가 0 인경우가 있으므로, 거듭제곱시 주의 (메모리 초과 이유)

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

typedef long long ll;

const ll mod = 1000000007; int T, N ,D;

struct Matrix{ int size; vector< vector > arr; Matrix(){ size = N; arr = vector< vector >(N, vector(N,0)); } Matrix operator * (const Matrix &x){ Matrix ret; for(int i=0; i<size; i++){ for(int j=0; j<size; j++){ for(int k=0; k<size; k++){ ret.arr[i][j] += arr[i][k] * x.arr[k][j]; ret.arr[i][j] %= mod; } } } return ret; } };

Matrix powmat(Matrix a, ll b){ if(b == 0) { Matrix I; for(int i = 0;i<N;i++) I.arr[i][i] = 1; return I; }; if(b == 1) return a; Matrix ret = powmat(a, b/2); ret = ret * ret; if(b & 1) ret = ret * a; return ret; }

int main(void){ cin » T » N »D; Matrix mat[101];

for(int i = 0;i<N;i++){
    mat[0].arr[i][i]= 1;
}

for(int i = 1; i<=T;i++){
    int M; cin >> M;
    while(M--){
        int a,b,c; cin >> a >> b >> c;
        a--; b--;
        mat[i].arr[a][b] = c;
    }
}
for(int i = 1; i<=T;i++){
    mat[0] = mat[0] * mat[i];
}
mat[0] = powmat(mat[0], 1LL * D / T);

for(int i = 1; i<= D%T;i++){
    mat[0] = mat[0] * mat[i];
}
for(int i = 0;i<N;i++){
    for(int j = 0;j<N;j++){
        cout << mat[0].arr[i][j] <<" ";
    }
    cout << "\n";
} } ```

BOJ 13876 - 타일채우기 2

3*N 을 채우는 개수의 점화식 수열
N이 매우 크므로, 일반적으로 $O(N)$ 으로는 구하기 어려움 -> 행렬로 바꾼 후 거듭제곱
https://angjong55.tistory.com/13 참고

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

typedef long long ll;

const ll mod = 1000000007;
ll N;


struct Matrix{
	int size;
	vector< vector<ll> > arr;
	Matrix(){size = 0;}
	Matrix(int n){
		size =n;
		arr = vector< vector<ll> >(n, vector<ll>(n,0));
	}
	Matrix operator * (const Matrix &x){
		Matrix ret(size);
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					ret.arr[i][j] += arr[i][k] * x.arr[k][j];
					ret.arr[i][j] = (ret.arr[i][j] +mod)% mod;
				}
			}
		}
		return ret;
	}
};

Matrix powmat(Matrix a, ll b){
	if(b == 1) return a;
	Matrix ret = powmat(a, b/2);
	ret = ret * ret;
	if(b & 1) ret = ret * a;
	return ret;
}


int main(void){
    cin >> N;
    if(N&1){
        cout << 0 <<"\n";
        return 0;
    }
    Matrix M(2),P(2);
    M.arr = { {4,-1} , {1,0} };
    P.arr = { {3,0} , {1,0} };
    M = powmat(M, N/2) * P;

    cout << M.arr[1][0] % mod;
    
}

BOJ 13430 - 합 구하기

$S(k,n) = {n+k} C{k+1}$ 와 같다.
간단히 이항계수 계산으로 풀어주면 됨
좀더 간단한 inv 계산 식 사용

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

typedef long long ll;
const ll mod = 1e9+7;

ll pow(ll n,ll k){
    ll ret = 1;
    k <<= 1;
    while(k >>= 1){
        if(k&1) ret = ret * n% mod;
        n = n*n % mod;
    }
    return ret;
}

ll fac(ll a,ll b){
    ll ret = 1;
    for(ll i = a; i<= b;i++){
        ret = ret* i % mod;
    }
    return ret;
}

int main(void){
    ll N, K;
    cin >> K >> N;
    
    ll ans = fac(N,N+K) * pow(fac(1,K+1),mod-2) % mod;
    cout << ans<< "\n";
}

24.04.23~26 문제풀이

24.04.23 ~ 26

KOI 2019 1차 대회 문제풀이 이제 조금씩 대회 문제무작위로 풀이하기 시작

BOJ 17609 - 회문

회문 판정 알고리즘 이용
dp 까지는 사용안해도 시간 안에 들어옴

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

string str;
int g(int i , int j){
    if (i >= j)
        return 0;
    if (str[i] != str[j]){
        return 2;
    }
    return g(i + 1, j - 1);
}
int f(int i,int j){
    if (i >= j)
        return 0;
    if (str[i] != str[j]){
        int ret1 = g(i+1, j);
        int ret2 = g(i, j-1);
        if(ret1 == 0 || ret2 == 0) return 1;
        else return 2;
    }
    return f(i + 1, j - 1);
}

int main(void){
    int T; cin >> T;
    while(T--){
        cin >> str;
        cout << f(0, str.size()-1) << "\n";
    }
}

BOJ 17610 - 양팔저울

브루트포스 알고리즘 문제

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

int N,sum, ans,S[14], c[4040404];

void f(int n, int k){
    if(n == N){
        if(k >0) c[k] =1;
        return;
    }
    f(n+1, k+S[n]);
    f(n+1, k-S[n]);
    f(n+1, k);
}

int main(void){
    cin >> N;
    
    for(int i = 0; i<N;i++) cin >> S[i];
    for(int i = 0; i<N;i++) sum += S[i];
    
    f(0,0);
    for(int i = 1;i<sum;i++){
        if(!c[i]) ans++;
    }
    cout <<ans <<"\n";
    
}

BOJ 17612 - 쇼핑몰

동일 순번인 경우 계산대가 큰 순서대로 퇴출 -> pq 사용
이후 작은 계산대부터 채워넣어야함 -> stack 사용
두개의 자료구조를 잘 사용하여 풀어야 하는 문제

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

int main(void){
    
    int N, K;
    cin >> N >> K;
    long long ans = 0;
    vector<pair<int,int>> v;
    priority_queue<tuple<int,int,int>> pq;
    for(int i = 1; i<=N;i++){
        int r,t;
        cin >> r >> t;
        v.push_back({r,t});
        if(i <= K) pq.push({-t,i,r});
    }
    int cnt = 1, idx = K;
    
    
    stack<pair<int,int>> s;
    while(!pq.empty()){
        int qr, qt, qcur; tie(qt,qcur,qr) = pq.top();
        qt *= -1;
        
        int nr,nt,ncur;
        nr = qr; nt = qt; ncur = qcur;
        while(!pq.empty() && qt == nt){
            s.push({nt, ncur});
            pq.pop();
            ans += 1LL * nr *( cnt++);
            
            tie(nt,ncur,nr) = pq.top();
            nt *= -1;
        }
        
        while(!s.empty()){
            if(pq.size() < K && idx < N){
                int nt = s.top().first, ncur = s.top().second;
                s.pop();
                pq.push({-(nt + v[idx].second), ncur, v[idx++].first});
            }
            else break;
        }
    }
    
    
    cout << ans;
}

24.04.27 문제풀이

24.04.27

sweeping 문제풀이

BOJ 1911 - 흙길 보수하기

스위핑 문제
물웅덩이 좌표를 시작좌표 기준으로 정렬한 후 왼쪽에서 부터 웅덩이가 있는 부분에 판자를 채워주면 됨

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int INF = 1e9+1;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N , L;
    vector <pair<ll,ll>> v;
    
    cin >> N >> L;
    for(int i = 0;i<N;i++){
        ll x, y; cin >> x >> y;
        v.push_back({x,y});
    }
    
    sort(v.begin(), v.end());
    
    ll ans= 0 ,cnt = 0, x = 0;
    
    for(int i = 0;i<N;i++){
        x = max(x, v[i].first);
        if( v[i].second < x) continue;
        int tmp = ceil((v[i].second- x)/ (double) L);
        ans += tmp;
        x += L*tmp;
        
    }
    cout << ans ;
    
}

BOJ 2170 - 선긋기

스위핑 기초문제

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int INF = 1e9+1;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    vector <pair<ll,ll>> v;
    
    cin >> N;
    for(int i = 0;i<N;i++){
        ll x, y; cin >> x >> y;
        v.push_back({x,y});
    }
    
    sort(v.begin(), v.end());
    
    ll ans = 0, l = -INF, r = -INF;
    
    for(int i = 0;i<N;i++){
        if(r < v[i].first){
            ans += r-l;
            l = v[i].first;
            r = v[i].second;
        }
        else r = max(r, v[i].second);
    }
    ans += r-l;
    cout << ans ;
    
}

BOJ 17619 - 개구리 점프

스위핑 문제
y좌표를 요구받지만, 문제에서는 y 좌표는 상관 없음 –> 선긋기 문제와 동일
인덱스별로 union-find 자료구조를 통해 집합을 만들어줌

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int INF = 1e9+1;

int par[101010];

void init(int n){
    for(int i = 1; i<=n;i++){
        par[i] = i;
    }
}

int find(int u){
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

void merge(int u,int v){
    u = find(u), v = find(v);
    if(u == v) return;
    par[u]  = v;
}


int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N , Q;
    vector <iii> v;
    
    cin >> N >> Q;
    for(int i = 0;i<N;i++){
        int x1, x2, y; cin >> x1 >> x2 >> y;
        v.push_back({x1,x2, i+1});
    }
    init(N);
    sort(v.begin(), v.end());
    int r = get<1>(v[0]);
    for(int i = 1; i<N;i++){
        int x1,x2, idx; tie(x1,x2,idx) = v[i];
        if(x1 <= r){
            merge(get<2>(v[i-1]), idx);
            r = max(r, x2);
        } 
        else r = x2;
    }
    
    
    while(Q--){
        int a,b; cin>> a >> b;
        cout << ( find(a) == find(b) ? 1 : 0) <<"\n";
    }
    
}

BOJ 10165 - 버스 노선

환형 스위핑 문제
개구리 점프를 환형으로 구현하면 됨
환형 인 경우, 노선을 0~N 을 0 ~ 2N 으로 연장 후 x1, x2를 입력 받고, $ x1 > x2 $ 일때 x2에 N 을 더해줌
$ x2 <= N $ 에 한해서 x1+N, x2+N 을 v에 넣어줌
이때 시작점은 오름차순, 끝점은 내림차순으로 정렬하기 위해 -를 붙여줌

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;


int ans[505050];


int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N , M;
    vector <iii> v;
    
    cin >> N >> M;
    for(int i = 0;i<M;i++){
        int x1, x2; cin >> x1 >> x2;
        if(x1 > x2) x2 += N;
        if(x2 <= N) v.push_back({x1+N, -(x2+N), i+1});
        v.push_back({x1,-x2, i+1});
        
    }
    sort(v.begin(), v.end());
    int l = 0, r = 0;
    for(int i = 0; i<v.size();i++){;
        int x1,x2, idx; tie(x1,x2,idx) = v[i];
        x2 *= -1;
        if(ans[idx]) continue;
        if(l <= x1 && x2 <= r){
            ans[idx] = true;
            continue;
        } 
        l = x1, r = x2;
    }
    for(int i = 1; i<=M;i++){
        if(!ans[i]) cout << i <<" ";
    }

}

KOI 2018 초등부 문제풀이 ( 24.04.29 )

총평

처음으로 풀어본 KOI 완셋이다 + 올클 확실히 실력이 많이 올랐음을 직감하였음 3번문제까지는 무난하게 풀었고, 4번 문제는 로직보단 자료구조를 어떤것을 사용할것인가 생각하는 것이 조금 오래 걸렸음

KOI 2018 초등부 1번

단순히 주어진 입력값에서 최대와 최소를 찾아서 차이를 구하는 문제
굳이 배열을 사용할 필요 없음

KOI 2018 초등부 2번

브루트포스로 풀수 있는 문제
$O(N^2)$ 의 시간복잡도를 가짐

KOI 2018 초등부 3번

정점이 N개 간선이 N-1개 이므로 트리 문제
dfs를 이용하여 시점과 종점을 잇는 길을 찾은 후, 해당 길에서 가장 큰 가중치를 가지는 값을 전체 path의 길이에서 빼주면 된다.
주의해야할건 시점과 종점이 같은 경우 바로 0으로 처리해주면 된다.

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

int N, s, e;
vector<pair<int,int>> g[101010];
vector<int> ans;
void dfs(int u, int p){
	if(u == e){
		int ret = 0;
		for(int i = 0; i<ans.size();i++){
			ret += ans[i];
		}
		int mx = *max_element(ans.begin(), ans.end());
		cout << ret - mx <<"\n";
		exit(0);
	}
	for(auto v : g[u]){
		if(v.first == p) continue;
		ans.push_back(v.second);
		dfs(v.first, u);
		ans.pop_back();
	}
}

int main(void){
	cin >> N >> s >> e;
	for(int i =0;i<N-1;i++){
		int u,v,w; cin >> u >> v >> w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	if (s == e) cout << 0<<"\n";
	else dfs(s,0);
}

KOI 2018 초등부 4번 (☆)

다익스트라 알고리즘을 변형하여 구현하면 되는 문제
다만, 어떤 자료구조를 사용할 것인가에 대해 코드가 복잡해질수 있음
인접리스트를 사용하여 각 NM 배열의 각 좌표를 1부터 NM에 대응시켜 품
외곽에 구멍이 있는 경우 0과 연결시켜 주었음
외곽과 연결된 곳들을 먼저 pq에 넣어주고 풀이 진행

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

int N , M ,H;
vector<pair<int,int>> g[1010101];
int V[1010101];

priority_queue<tuple<int,int,int>> pq;

int main(void){
    cin >> N >> M >> H;
	V[0] = 0;
    for(int i = 1; i<= N+1;i++){
        for(int j = 1; j<=M;j++){
            int k; cin >> k;
            if(k != -1){
                int idx = (i-1)*M +j;
                g[(idx <=N*M ? idx : 0)].push_back({(idx-M > 0 ? idx-M : 0),k});
                g[(idx-M > 0 ? idx-M : 0)].push_back({(idx <=N*M ? idx : 0),k});
            }
        }
    }
    for(int i = 1; i<= N;i++){
        for(int j = 1; j<=M+1;j++){
            int k; cin >> k;
            if(k != -1){
                int idx = (i-1)*M +j;
                g[(j == M+1 ? 0 : idx)].push_back({(j == 1 ? 0 : idx-1),k});
                g[(j == 1 ? 0 : idx-1)].push_back({(j == M+1 ? 0 : idx),k});
            }
        }
    }
	for(int i = 1; i<=N*M;i++){
	    V[i] = H;
		for(auto k : g[i]){
			if(k.first == 0){
				pq.push({-k.second, i, k.first});
			}
		}
	}
    while(!pq.empty()){
        int h, c, p; tie(h,c,p) = pq.top();
        h *= -1;
        pq.pop();
        if(V[c] > max(h, V[p])){
            V[c] = max(h,V[p]);
            for(auto nxt : g[c]){
            	if(nxt.first == 0) continue;
                pq.push({-nxt.second, nxt.first, c});
            }
        }
    }
    int ans = 0;
    for(int i = 1; i<=N*M;i++) ans += V[i];
    cout << ans;
}

Lazy Propagation을 Bottom up 으로 구현

BOJ 10999 - 구간 합 구하기 2

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

typedef long long ll;

ll t[4040400], d[4040400];
ll n,h;

void calc(ll p, ll k) {
  if (d[p] == 0) t[p] = t[p<<1] + t[p<<1|1];
  else t[p] = d[p] * k;
}

void apply(ll p, ll value, ll k) {
  t[p] += value * k;
  if (p < n) d[p] += value;
}
void build(ll l, ll r) {
  ll k = 2;
  for (l += n, r += n-1; l > 1; k <<= 1) {
    l >>= 1, r >>= 1;
    for (ll i = r; i >= l; --i) calc(i, k);
  }
}

void push(ll l, ll r) {
  ll s = h, k = 1 << (h-1);
  for (l += n, r += n-1; s > 0; --s, k >>= 1)
    for (ll i = l >> s; i <= r >> s; ++i) if (d[i] != 0) {
      apply(i<<1, d[i], k);
      apply(i<<1|1, d[i], k);
      d[i] = 0;
    }
}

void modify(ll l, ll r, ll value) {
  if (value == 0) return;
  push(l, l + 1);
  push(r - 1, r);
  bool cl = false, cr = false;
  ll k = 1;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
    if (cl) calc(l - 1, k);
    if (cr) calc(r, k);
    if (l&1) apply(l++, value, k), cl = true;
    if (r&1) apply(--r, value, k), cr = true;
  }
  for (--l; r > 0; l >>= 1, r >>= 1, k <<= 1) {
    if (cl) calc(l, k);
    if (cr && (!cl || l != r)) calc(r, k);
  }
}

ll query(int l, int r) {
  push(l, l + 1);
  push(r - 1, r);
  ll res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) res += t[l++];
    if (r&1) res += t[--r];
  }
  return res;
}
int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, M ,K; cin >> N >> M >> K;
	
	
	n = 1;
	while(n < N) n <<=1;
	h = sizeof(int) * 8 - __builtin_clz(n);
	for(ll i = 0;i<N;i++) cin >> t[i+n];
	for(int i = n-1;i;--i) t[i] = t[i<<1]+t[i<<1|1];
	int T = M+K;
	while(T--){
		int a;
		cin >> a;
		if(a == 1){
			ll b,c,d;
			cin >> b >> c >> d;
			
			modify(b-1,c,d);
		}
		if(a == 2){
			ll b,c;
			cin>> b >> c;
			cout << query(b-1,c)<<"\n";
		}
	}
}

4월의 마지막 달 문제

앞으로 5월부터는 주차별로 풀이를 올려야겠다.

BOJ 6549 - 히스토그램에서 가장 큰 직사각형

segment Tree에는 최소값의 인덱스를 저장해야함
분할정복을 이용하여 넓이의 최대값을 구해주면 됨 –> 포인트

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

typedef long long ll;
const int INF = 1e9+3;
ll t[404040], A[101010];
ll n;

inline ll combine(ll a, ll b){
	int ta = (a==-1 ? INF : A[a]);
	int tb = (b == -1 ? INF : A[b]);
	if(ta <= tb) return a;
	else return b;
}

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = combine(t[i<<1], t[i<<1 | 1]);
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>>=1;) t[p] = combine( t[p<<1], t[p<<1|1]);
}

ll query(int l, int r){
	ll resl = -1, resr = -1;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) resl = combine(resl, t[l++]); 
		if(r&1) resr = combine(t[--r], resr);
	}
	return combine(resl, resr);
}

ll largest(int s, int e){
    
	int m = query(s,e+1);
	ll area = (e-s+1)*A[m]*1LL;
	if(s <= m-1) {
		ll temp = largest(s,m-1);
		area = max(area, temp);
	}
	if(m+1 <= e){
		ll temp = largest(m+1, e);
		area = max(area, temp);
	}
	return area;
}


int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	int N;
	while(true){
		cin >> N;
		if(N == 0) break;
		n = 1;
		while(n < N) n <<=1;
		for(ll i = 0;i<N;i++){
			cin >> A[i];
			t[i+n] = i;
		};
		for(ll i = N;i<n;i++) A[i] = INF,  t[i+n] = i;
		build();
		cout << largest(0,N-1)<<"\n";
	}
	
}

BOJ 5676 - 음주 코딩

곱한 값은 수가 커질 수 있으므로, 양수인 경우 1, 음수인 경우 -1 로 바꿔서 세그먼트 트리에 저장한다.

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

typedef long long ll;

ll t[4040400];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] * t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>>=1;) t[p] = t[p<<1]* t[p<<1|1];
}

ll query(int l, int r){
	ll res =1;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) res *= t[l++];
		if(r&1) res *= t[--r];
	}
	return res;
}

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	int N,K;
	while(cin >> N  >>  K){
		
		n = 1;
		while(n < N) n <<=1;
		for(ll i = 0;i<N;i++){
			int tmp; cin >> tmp;
			t[i+n] = (tmp >= 0 ?(tmp == 0 ? 0 : 1) :-1 );
		};
		for(ll i = N;i<n;i++) t[i+n] = 1;
		build();
		
		while(K--){

			char C;
			int i,j; cin >> C >> i >> j;
			if(C == 'C'){
				update(i-1,(j == 0 ? 0 : (j > 0 ? 1 : -1)));
			}
			else{
				int temp = query(i-1,j);
				if(temp == 0) cout << 0;
				else if(temp == 1) cout << '+';
				else cout << '-';
			}
			
		}
		cout << "\n";
		
	}
	
}

2024년 5월 문제풀이 (최근 수정 : 2024.05.04)

BOJ 12837 - 가계부 (Hard)

세그먼트 트리
p의 위치의 값을 v로 바꾸는 것이 아닌 p의 값 에 v를 더해야함
트리의 기본값은 0이므로 따로 수를 추가할 필요가 없음

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

ll t[4040400];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}

ll query(int l, int r){
	ll res = 0;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) res += t[l++];
		if(r&1) res += t[--r];
	}
	return res;
}

int main(void){
	FASTIO
	int N, Q;
	cin >> N >>Q;
	
	n = 1;
	while(n < N) n <<=1;
	while(Q--){
		ll a,b,c; cin >> a >> b  >> c;
		if(a&1) update(b-1,t[b-1+n] + c);
		else cout <<  query(b-1,c) <<"\n";
	}
}

BOJ 1275 - 커피숍2

세그먼트 트리
x와 y의 값이 바뀔수도 있으므로 주의해야함

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

ll t[4040400];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}

ll query(int l, int r){
	ll res = 0;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) res += t[l++];
		if(r&1) res += t[--r];
	}
	return res;
}

int main(void){
	FASTIO
	int N, Q;
	cin >> N >>Q;
	
	n = 1;
	while(n < N) n <<=1;
	for(ll i = 0;i<N;i++) cin >> t[i+n];
	build();
	while(Q--){
		ll x,y,a,b; cin >> x  >> y >> a >> b;
		if(x>y) swap(x,y);
		cout << query(x-1,y) <<"\n";
		update(a-1, b);
	}
}

BOJ 1517 - 버블 소트

세그먼트 트리 문제
swap의 개수 = 원배열과 정배열(정렬된)을 같은 수끼리 이어나갈때, 교차점의 개수를 세는 것과 같음 –> Inversion counting 이라 한다함
트리의 기본값을 모두 1로 해놓고, [0, 원배열(i)) 의 1의 합을 구한 후, 원배열(i)를 0으로 바꿔주면 됨
좌표 압축을 통해 간단히 변형

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

ll t[4040400];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}

ll query(int l, int r){
	ll res = 0;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) res += t[l++];
		if(r&1) res += t[--r];
	}
	return res;
}

int main(void){
	FASTIO
	int N;
	cin >> N;
	vector<pair<int,int>> v(N);
	n = 1;
	while(n < N) n <<=1;
	
	for(int i = 0;i<N;i++){
		int k; cin >> k;
		v[i] = {k,i};
		t[i+n] = 1;
	}
	build();
	sort(v.begin(), v.end());
	vector<int> c(N);
	for(int i = 0; i<N;i++){
		int a,b; tie(a,b) = v[i];
		c[b] = i;
	}
	ll ans = 0;
	for(int i = 0;i<N;i++){
		
		ans += query(0, c[i]);
		update(c[i], 0);
	}
	cout << ans <<"\n";
}

BOJ 3006 - 터보 소트

세그먼트 트리
버블 소트 문제와 비슷하지만, 1 -> N -> 2 -> N-2 … 식으로 지나갈때 하나는 [0, ~) , 그리고 [ ~+1, N) 의 쿼리들을 계산 해주면 됨

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

ll t[4040400];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}

ll query(int l, int r){
	ll res = 0;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) res += t[l++];
		if(r&1) res += t[--r];
	}
	return res;
}

int main(void){
	FASTIO
	int N;
	cin >> N;
	vector<int > c(N);
	n = 1;
	while(n < N) n <<=1;
	
	for(int i = 0;i<N;i++){
		int k; cin >> k;
		c[k-1] = i;
		t[i+n] = 1;
	}
	build();
	for(int i = 0, j = N-1; i<=j; i++, j--){
		cout << query(0, c[i]) <<"\n";
		update(c[i],0);
		if(i !=j){
			cout <<  query(c[j]+1, N) <<"\n";
			update(c[j], 0);
		}

	}
	
}

BOJ 2243 - 사탕상자

이분탐색으로 순위에 맞는 사탕을 찾아야함
이분탐색중, 해당 구간의 최댓값이 순위보다 작은경우, 순위- 구간 최댓값을 탐색에 넣어야함

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

ll t[3030300];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}

int q(int node, int k ){
	if(node >= n) return node - n;
	if(t[node*2] >= k) return q(node *2 , k);
	else return q(node*2 +1 , k - t[node*2]);
}

int main(void){
	FASTIO
	int N,M;
	cin >> M;
	N = 1000001;
	n = 1;
	while(n < N) n <<=1;
	
	while(M--){
		int a,b,c, tmp;
		cin >> a;
		if(a == 1){
			cin >> b;
			cout << (tmp = q(1,b))<<"\n";
			update(tmp, t[tmp+n] -1);			
		}
		else{
			cin >> b >> c;
			update(b,t[b+n]+c);
		}
	}
}

BOJ 7578 - 공장

Inversion counting 문제 ```cpp #include <bits/stdc++.h> #define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); using namespace std;

typedef long long ll;

ll t[4040400]; ll n;

void build(){ for(ll i = n-1;i>0;–i ) t[i] = t[i«1] + t[i«1 | 1]; } void update(ll p, ll v){ for(t[p+=n] = v; p>1; p»= 1) t[p»1] = t[p] + t[p^1]; }

ll query(int l, int r){ ll res = 0; for(l += n, r+= n; l<r;l»=1, r»= 1){ if(l&1) res += t[l++]; if(r&1) res += t[–r]; } return res; }

int main(void){ FASTIO int N; cin » N; vector tmp(5050500), arr(5050500); n = 1; while(n < N) n <<=1;

for(int i = 0;i<N;i++){
	int k; cin >> k;
	tmp[k] = i;
}
for(int i = 0;i<N;i++){
	int k; cin >> k;
	arr[tmp[k]]  = i;
}
build();
ll ans = 0;
for(int i = 0;i<N;i++){
	
	ans += query(arr[i]+1, N);
	update(arr[i], 1);
}
cout << ans <<"\n"; } ```

2024년 5월 문제풀이 #2 (최근 수정 : 2024.05.10)

KMP algorithm

https://justicehui.github.io/hard-algorithm/2019/01/16/KMP/ 참고

문자열 매칭 알고리즘을 $O(SP)$ 보다 빠르게 풀수 있는 알고리즘

PI[i] : 0~i 까지 문자열의 preffix와 suffix의 공통되는 길이의 max 를 저장
문자열 S와 P의 공통되는 부분까지 가다가 만약, 다른 부분이 생기면 체인을 이용하여 S[i]와 P[i]가 같아질때까지 공통구간의 길이로 줄여나감

BOJ 1786 - 찾기

kmp
공백이 있는 문자열이 들어오므로 getline() 이용

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

vector<string> prefix(string str){
    int n = str.size();
    vector<string> p;
    string tmp = ""; tmp+= str[0];
    p.push_back(tmp);
    for(int i = 1; i<n;i++){
        p.push_back(p.back() + str[i]);
    }
    return p;
}
vector<string> suffix(string str){
    int n = str.size();
    vector<string> s;
    string tmp = ""; tmp+= str.back();
    s.push_back(tmp);
    for(int i = n-2; i>=0;i--){
        s.push_back(str[i] + s.back());
    }
    return s;
}

vector<int> pi(string str){
    int n = str.size();
    vector<int> p(n);
    
    p[0] = 0;
    int j = 0;
    for(int i = 1; i<n;i++){
        while(j > 0 && str[i] != str[j]) j = p[j-1];
        if(str[i] == str[j]){
            p[i] = j+1;
            j++;
        }
    }
    return p;
}

vector<int> kmp (string s, string p){
    vector<int> ans;
    int n = s.size(), m = p.size();
    vector<int> PI = pi(p);
    int j = 0;
    for(int i = 0; i<n;i++){
        while(j > 0 && s[i]!= p[j]) j = PI[j-1];
        if(s[i] == p[j]){
            if(j == m-1){
                ans.push_back(i-m+1);
                j = PI[j];
            }
            else j++;
        }
    }
    return  ans;
}

int main(void){
    string s,p;
    
    getline(cin, s);
    getline(cin, p);
    
    vector<int> ans = kmp(s,p);
    
    cout << ans .size()<<"\n";
    for(auto i : ans) cout << (i+1) <<" ";
}

BOJ 1305 - 광고

PI 배열 응용
순간 전광판 : 광고 + 광고 접미사 –> 전광판 길이 - PI[전광판 길이 - 1]

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

vector<string> prefix(string str){
    int n = str.size();
    vector<string> p;
    string tmp = ""; tmp+= str[0];
    p.push_back(tmp);
    for(int i = 1; i<n;i++){
        p.push_back(p.back() + str[i]);
    }
    return p;
}
vector<string> suffix(string str){
    int n = str.size();
    vector<string> s;
    string tmp = ""; tmp+= str.back();
    s.push_back(tmp);
    for(int i = n-2; i>=0;i--){
        s.push_back(str[i] + s.back());
    }
    return s;
}

vector<int> pi(string str){
    int n = str.size();
    vector<int> p(n);
    
    p[0] = 0;
    int j = 0;
    for(int i = 1; i<n;i++){
        while(j > 0 && str[i] != str[j]) j = p[j-1];
        if(str[i] == str[j]){
            p[i] = j+1;
            j++;
        }
    }
    return p;
}

vector<int> kmp (string s, string p){
    vector<int> ans;
    int n = s.size(), m = p.size();
    vector<int> PI = pi(p);
    int j = 0;
    for(int i = 0; i<n;i++){
        while(j > 0 && s[i]!= p[j]) j = PI[j-1];
        if(s[i] == p[j]){
            if(j == m-1){
                ans.push_back(i-m+1);
                j = PI[j];
            }
            else j++;
        }
    }
    return  ans;
}

int main(void){
    int N;
    cin >> N;
    string S; cin >> S;
    
    auto ans = pi(S)[N-1];
    cout << N - ans<<"\n";
}

BOJ 3653 - 영화수집

segment tree 문제
segment tree에 할당되는 칸을 N+M으로 한후, n+M 부터 1을 넣어준다 (기본)
$p[i] : i번째 책이 트리 안에 있는 위치$
이후 query(0 ~ p[i]) 으로 p[i]보다 앞에 있는 1의 합을 구해준다.
update(p[i], 0), update(M–, 1) : p[i]의 책을 M 위치로 보내준다.
위 과정을 하면 보다 쉽게 책의 위치가 바뀐것을 알수 있다.
p[i] = M

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

typedef long long ll;

ll t[4040400];
int p[101010];
ll n;

void build(){
	for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
	for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}

ll query(int l, int r){
	ll res = 0;
	for(l += n, r+= n;  l<r;l>>=1, r>>= 1){
		if(l&1) res += t[l++];
		if(r&1) res += t[--r];
	}
	return res;
}


int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int TC; cin >> TC;
	while(TC--){
		memset(t, 0, sizeof(t));
		memset(p, 0 , sizeof(p));
		int N, M;
		cin >> N >> M;
		n = 1;
		while(n < N+M) n <<=1;
		for(int i = 0;i<N;i++){
			t[i+n+M] = 1;
			p[i+1] = i+M;
		}
		
		build();
		
		while(M--){
			int tmp; cin >> tmp;
			
			cout << query(0, p[tmp])<< " ";
			update(p[tmp],0);
			update(M-1, 1);
			p[tmp] = M-1;
		}
		cout << "\n";
	}
}

BOJ 12851 - 숨바꼭질 2

숨바꼭질 1과 같은 문제
queue < tuple< int, int ,int » 형태로 현재위치, 카운트, 이전위치를 저장해줌
1에서 출발하는 경우 2배한것과 +1 이 같음 –> vt[cur]로만 처리할 경우, 중복으로 카운트 안됨

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

bool vt[101010];
ll N, K, mn = 1e6+1, ans;

int main(void){
	
	cin >> N >> K;
	
	queue<tuple<ll, ll, ll>> q;
	q.push({N,0,100001});
	
	while(!q.empty()){
		ll cur, t, prv; tie(cur,t, prv) = q.front();
		if(prv != K) vt[prv] = true;
		q.pop();
		if(cur > 100000 || cur < 0 || vt[cur]) continue;
		if(cur == K){
			if(mn > t) ans = 1, mn = t;
			else if(mn == t) ans++;
		}
		
		if(t > mn) break;
		q.push({cur+1, t+1,cur});
		q.push({cur-1, t+1,cur});
		q.push({cur << 1, t+1,cur});
		
	}
	cout << mn << "\n" << ans <<"\n";
}

BOJ 13913 - 숨바꼭질 4

경로 추적 + 숨바꼭질 1
숨바꼭질 2 문제의 코드와 다르게, bfs 를 구성해보았음
다양한 형태의 bfs와 bfs에서 경로추적 코드 기억

#include <bits/stdc++.h>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;

ll N, K;
deque<int> ans;
int d[101010], p[101010];
int main(void){
	FASTIO
	cin >> N >> K;
	
	queue<int> q;

	memset(d, -1, sizeof(d));
	
	d[N] = 0;
	p[N] = N;
	q.push(N);
	
	while(d[K] == -1){
		int cur = q.front(); q.pop();
		for(int nxt : {cur-1, cur+1, cur <<1}){
			if(nxt < 0 || nxt > 100000 || d[nxt] != -1) continue;
			d[nxt] = d[cur]+1;
			p[nxt] = cur;
			q.push(nxt);
		}
	}
	cout << d[K] <<"\n";
	ans.push_front(K);
	
	while(ans.front() != N){
		ans.push_front(p[ans.front()]);
	}
	for(int i : ans) cout << i <<" ";
} 

BOJ 11692 - 시그마 함수

sol. 1 풀이

시간복잡도 : $O(\sqrt(N)M)$ –> TLE

M이 매우 크기 때문에 M에 대해 전체 탐색을 하는것은 잘못된 선택이다

sol. 2 풀이

시간복잡도 : $O(log M)$

$n = 2^x p_{1}^{e_1} p_{2}^{e_2} p_{3}^{e_3} … p_{k}^{e_k}$ 으로 정의할 수 있다. 이때 $p_i$는 홀수이다.

여기서 약수의 합은 다음처럼 구할 수 있다.

$(1+2+2^2 + … + 2^x) (1+p_{1} + p_{1}^2 … p_{1}^{e_1})…(1+p_{k} + p_{k}^2 … p_{k}^{e_k})$ 이때 첫번째 항은 무조건 홀수 이다. 그러므로 나머지 항 중 하나라도 짝수여야 n 이 짝수다.

이 말은 $e_k$ 중 하나라도 홀수면 n 이 짝수라는 뜻이다.

우리는 문제를 풀때 전체 개수에서 홀수인 개수를 빼도 정답을 구할 수 있다.

즉 $e_k$ 가 모두 짝수일 때를 구하면 된다.

근데 $e_k$가 모두 짝수라는건 결국 $n = P^2 2^x$ 와 같다. 이때 $P$는 홀수 이다.

$m \geq P^2 2^x$의 개수를 구해야 한다.

$ m / {2^x} \geq P^2$ 에서 각 $x$마다의 $P$의 개수를 구하면 되므로

홀수 $P$의 개수는 $(\sqrt(m) +1 )/2$와 같다.

즉 $m$을 2로 나누면서 해당 식의 값을 찾아주면 된다.

sol.3 풀이

$O(1)$

위의 수식을 다시 생각해보면 $n = P^2 2^x$ 이다. 근데 x가 홀수일 때, 짝수일 때 생각하면?

$n = X^2 or 2X^2$ 이다. 이때 $X$는 자연수이다. 즉 전체에서 다음 두가지를 만족하는 수의 개수를 빼주면 되므로

$O(1)$에 처리가 가능하다.

#include <bits/stdc++.h>

using namespace std;

int main(void){
    
    long long m;
    cin >> m;
    
    cout << m - (long long)sqrt(m) - (long long)sqrt(m/2);
}