BOJ 20040 : 사이클 게임 (Gold 4)

• 번 DFS를 돌려서 사이클을 조사하는 것은 비효율적이다. Disjoint Set을 활용하도록 하자.

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

using vi = vector<int>;

struct DisjointSet {
  vi parent, rank;

  DisjointSet(int n) {
    rank.resize(n, 1);
    parent.resize(n);
    for (int i=0;i<n;i++)
      parent[i]=i;
  }

  int find(int x) {
    if (parent[x]==x) return x;
    return parent[x]=find(parent[x]);
  }

  void merge(int x, int y) {
    x=find(x), y=find(y);
    if (rank[x]>rank[y]) swap(x,y);
    parent[x]=y;
    rank[y]+=rank[x];
  }
};

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

  int n, m; cin >> n >> m;

  DisjointSet ds(n);
  for (int i=1;i<=m;i++) {
    int x, y; cin >> x >> y;
    if (ds.find(x) == ds.find(y)) {
      cout << i; return 0;
    } else {
      ds.merge(x, y);
    }
  }
  cout << 0;

  return 0;
}

BOJ 5615 : 아파트 임대 (Platinum 1)

• 면적을 라 하면 다음과 같이 식을 변형할 수 있다.

• 을 1보다 큰 홀수 두 개로 쪼갤 수 있는가, 즉 이 소수인가를 판정하면 된다.

• 에라토스테네스의 체는 느리다. 밀러-라빈 소수 판정법을 사용하면 된다.

• 시간 복잡도는 이 된다.

  • 는 밀러-라빈 소수 판정에 사용되는 밑 의 개수로, 결정론적 알고리즘에는 최소 12가 필요하며,
  • 는 miller_rabin 함수 내의 반복문의 횟수로, 이진수로 나타냈을 때의 자리수이다. 문제의 조건상 32이다.

• 로 비교적 아슬하게 TLE를 면할 수 있다.

#include <bits/stdc++.h>

using namespace std;

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpow(u64 base, u64 e, u64 mod) {
  u64 result = 1;
  base %= mod;
  while (e) {
    if (e & 1)
      result = (u128)result * base % mod;
    base = (u128)base * base % mod;
    e >>= 1;
  }
  return result;
}

bool miller_rabin(u64 n, u64 a, u64 d, int s) {
  u64 x = binpow(a, d, n);
  if (x == 1 || x == n - 1)
    return false;
  for (int r = 1; r < s; r++) {
    x = (u128)x * x % n;
    if (x == n - 1)
      return false;
  }
  return true;
};

bool is_prime(u64 n) {
  if (n < 2)
    return false;

  int r = 0;
  u64 d = n - 1;
  while ((d & 1) == 0) {
    d >>= 1;
    r++;
  }

  for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
    if (n == a)
      return true;
    if (miller_rabin(n, a, d, r))
      return false;
  }
  return true;
}

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

  int n; cin>>n;

  int cnt = 0;
  for (int i=0; i<n; i++) {
    u64 x; cin>>x;
    cnt += is_prime(2*x+1);
  }

  cout << cnt;

  return 0;
}

• 원본 문제에서는 밀러-라빈을 의도한 것은 아닌 것으로 추정된다.

BOJ 2332 : 전화번호 (Gold 4)

• 다음 그래프를 떠올릴 수 있다.

  

• 다익스트라 사용하면 될 것 같다!

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

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

const int INF = numeric_limits<int>::max();

char to_num(char ch) {
  if (ch == 'o' || ch == 'q' || ch == 'z') return '0';
  if (ch == 'i' || ch == 'j') return '1';
  if (ch == 'a' || ch == 'b' || ch == 'c') return '2';
  if (ch == 'd' || ch == 'e' || ch == 'f') return '3';
  if (ch == 'g' || ch == 'h') return '4';
  if (ch == 'k' || ch == 'l') return '5';
  if (ch == 'm' || ch == 'n') return '6';
  if (ch == 'p' || ch == 'r' || ch == 's') return '7';
  if (ch == 't' || ch == 'u' || ch == 'v') return '8';
  if (ch == 'w' || ch == 'x' || ch == 'y') return '9';
  return '-';
}

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

  string s; cin >> s;
  int l = s.length();
  vector<vector<pi>> G(l+1); // +1 : terminal

  int n; cin >> n;
  vector<string> words(n);
  for (int i=0;i<n;i++) {
    cin >> words[i];
    int wl=(int)words[i].length();
    for (int j=0;j<l-wl+1;j++) {
      bool okay=true;
      for (int k=0;k<wl;k++) {
        if (s[j+k] != to_num(words[i][k])) {
          okay=false; break;
        }
      }
      if (okay) G[j].emplace_back(j+wl,i);
    }
  }

  priority_queue<pi, vector<pi>, greater<>> pq;
  vi dist(l+1, INF);
  vector<bool> visited(l+1, false);
  vector<pi> pred(l+1, {-1, -1});
  dist[0]=0;
  pq.emplace(0, 0);
  while (!pq.empty()) {
    int u=pq.top().second; pq.pop();
    if (visited[u]) continue;
    visited[u] = true;
    for (auto [v, w_idx] : G[u]) {
      if (dist[u]+1<dist[v]) {
        dist[v]=dist[u]+1;
        pred[v]={u,w_idx};
        pq.emplace(dist[v], v);
      }
    }
  }

  if (pred[l].first == -1) {
    cout << "0\nNo solution.";
    return 0;
  }

  vi sol;
  int cur=l;
  while (cur!=-1) {
    if (pred[cur].second != -1)
      sol.insert(sol.begin(), pred[cur].second);
    cur=pred[cur].first;
  }

  cout << sol.size() << '\n';
  for (int w_idx : sol) {
    cout << words[w_idx] << '\n';
  }

  return 0;
}

BOJ 7662 : 이중 우선순위 큐 (Gold 4)

• min heap, max heap을 각각 두어 lazy하게 동기화 시키면 된다.
• 마지막 동기화 잊지 않기!

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

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

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

  int T; cin >> T;
  while (T--) {
    bitset<1'000'000> has;
    priority_queue<pi> pq_less;
    priority_queue<pi, vector<pi>, greater<>> pq_greater;
    int cnt=0;
    int k; cin >> k;
    while (k--) {
      char cmd; cin >> cmd;
      if (cmd == 'I') {
        int x; cin >> x;
        pq_less.emplace(x, cnt);
        pq_greater.emplace(x, cnt);
        has[cnt] = true;
        cnt++;
      } else {
        int which; cin >> which;
        if (which == 1) {
          while (!pq_less.empty() && !has[pq_less.top().second])
            pq_less.pop();
          if (!pq_less.empty()) {
            has[pq_less.top().second] = false;
            pq_less.pop();
          }
        } else {
          while (!pq_greater.empty() && !has[pq_greater.top().second])
            pq_greater.pop();
          if (!pq_greater.empty()) {
            has[pq_greater.top().second] = false;
            pq_greater.pop();
          }
        }
      }
    }
    if (has.count() == 0) {
      cout << "EMPTY\n";
    } else {
      while (!pq_less.empty() && !has[pq_less.top().second])
        pq_less.pop();
      while (!pq_greater.empty() && !has[pq_greater.top().second])
        pq_greater.pop();
      cout << pq_less.top().first << ' ' << pq_greater.top().first << '\n';
    }
  }

  return 0;
}

BOJ 1904 : 01타일 (Silver 3)

• ‘동적 계획법’ 단계를 마저 풀어보자.

• 다음 점화식이 생각나지 않을 수 없다.

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

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

int dp[1'000'001] = {0, };

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

  int n; cin >> n;
  dp[1]=1;
  dp[2]=2;
  for (int i=3;i<=n;i++) {
    dp[i] = (dp[i-2] + dp[i-1]) % 15746;
  }

  cout << dp[n];

  return 0;
}

BOJ 9184 : 신나는 함수 실행 (Silver 2)

• 메모메모

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

map<int, int> memo;
int w(int a, int b, int c) {
  if (a <= 0 || b <= 0 || c <= 0) return 1;
  if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
  if (memo.count(a*10000+b*100+c)) return memo[a*10000+b*100+c];
  if (a < b && b < c) return memo[a*10000+b*100+c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
  return memo[a*10000+b*100+c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}

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

  int a, b, c;
  while (cin >> a >> b >> c, a != -1 || b != -1 || c != -1)
    cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << '\n';

  return 0;
}

BOJ 24416 : 알고리즘 수업 - 피보나치 수 1 (Bronze 1)

• 코드1은 번, 코드2는 번 실행된다.

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

int F[41]={0,};

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

  int n; cin >> n;
  F[1]=F[2]=1;
  for (int i=3;i<=n;i++)
    F[i]=F[i-1]+F[i-2];
  cout << F[n] << " " << n-2;

  return 0;
}

• 이로써 ‘동적 계획법 1’ 단계를 모두 해결하였다.

BOJ 33632 : 2교시: 체육 (Silver 1)

• 반례를 못 찾아서 업솔빙했다.

w, h = map(int, input().split())
x0, y0 = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

if y0 == 0 or y0 <= y1:
  print(0)
else:
  left = (y1 * x0) / y0
  right = w + y1*(x0-w)/y0
  if left > right:
    left, right = right, left
  if right <= x1 or x2 <= left:
    print(0)
  else:
    l = max(left, x1)
    r = min(right, x2)
    prob = (r - l) / (right - left)
    print(f"{prob:.12f}")

BOJ 2987 : 사과나무 (Gold 4)

def cross(a, b):
    return (a[1]*b[2]-a[2]*b[1], -a[0]*b[2]+a[2]*b[0], a[0]*b[1]-a[1]*b[0])

xa, ya = map(int, input().split())
xb, yb = map(int, input().split())
xc, yc = map(int, input().split())
area = abs(xa*(yb-yc)+xb*(yc-ya)+xc*(ya-yb))/2
print(round(area, 1))

n = int(input())
v1=(xb-xa, yb-ya, 0)
v2=(xc-xb, yc-yb, 0)
v3=(xa-xc, ya-yc, 0)

cnt = 0
for _ in range(n):
    x, y = map(int, input().split())
    c1 = cross(v1, (x-xa, y-ya, 0))[2]
    c2 = cross(v2, (x-xb, y-yb, 0))[2]
    c3 = cross(v3, (x-xc, y-yc, 0))[2]
    if c1<=0 and c2<=0 and c3<=0 or c1>=0 and c2>=0 and c3>=0:
        cnt+=1
print(cnt)

BOJ 2473 : 세 용액 (Gold 3)

• 두 용액 합을 미리 sums에 담아두고, 이진 탐색을 통해 세 용액을 찾는 문제이다.
• arr를 이분탐색하느냐, sums를 이분탐색하느냐를 고민해야 한다.
  • sums를 이분탐색하면 중복을 피하기 위해 최대 번 움직여야 하는데, 시간 초과가 나올 수 있다.
  • arr를 이분탐색하면 중복을 피하기 위해 최대 번만 움직이면 된다.
• arr를 이분탐색하면 이 된다.

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

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

const ll INF = numeric_limits<ll>::max();

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());

  vector<pair<ll, pi>> sums; // {arr[x]+arr[y], {x, y}}
  sums.reserve(n*(n-1)/2);
  for (int i=0;i<n;i++)
    for (int j=i+1;j<n;j++)
      sums.push_back({arr[i] + arr[j], {i, j}});
  int sumSize=(int)sums.size();

  ll m = INF;
  array<int,3> ans{-1,-1,-1};
  for (int i=0;i<sumSize;i++) {
    int l=0,r=n;
    ll x=-sums[i].first;
    while (l<r) {
      int mid=l+(r-l)/2;
      if (arr[mid] < x) {
        l = mid+1;
      } else {
        r = mid;
      }
    }
    int idx;
    if (l == 0) {
      idx = 0;
    } else if (l == n) {
      idx = n-1;
    } else if (abs(arr[l]-x)<abs(arr[l-1]-x)) {
      idx = l;
    } else {
      idx = l-1;
    }
    if (idx == sums[i].second.first || idx == sums[i].second.second) {
      l=idx-1;
      r=idx+1;
      if (l == sums[i].second.first || l == sums[i].second.second)
        l--;
      if (r == sums[i].second.first || r == sums[i].second.second)
        r++;
      if (l>=0) {
        ll sum = abs(sums[i].first + arr[l]);
        if (sum < m)
          m = sum, ans = {arr[sums[i].second.first], arr[sums[i].second.second], arr[l]};
      }
      if (r<n) {
        ll sum = abs(sums[i].first + arr[r]);
        if (sum < m)
          m = sum, ans = {arr[sums[i].second.first], arr[sums[i].second.second], arr[r]};
      }
    } else {
      ll sum = abs(sums[i].first + arr[idx]);
      if (sum < m)
        m = sum, ans = {arr[sums[i].second.first], arr[sums[i].second.second], arr[idx]};
    }
  }

  sort(ans.begin(), ans.end());
  for (int i=0;i<3;i++)
    cout << ans[i] << ' ';

  return 0;
}

• 이 방식으로 풀면, 상당히 귀찮기도 하고 이분탐색을 하면서 실수할 여지가 많다. (실제로도 많이 했다...) 대신, 으로 푸는 방법이 있다.
• 일종의 쓰리 포인터 느낌인데, 우선 ‘두 용액’ 문제를 투 포인터로 다시 풀어보자.

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

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

const int INF = numeric_limits<int>::max();

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 l=0, r=n-1, m=INF;
  pi ans;
  while (l<r) {
    int sum=arr[l]+arr[r];
    if (abs(sum)<m)
      m=abs(sum), ans={arr[l],arr[r]};

    if (sum<0) {
      l++;
    } else {
      r--;
    }
  }

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

  return 0;
}

• 여기서 sum의 부호에 따라 l과 r을 움직이는 이유는...

  • sum이 음수일 때에는, sum을 덜 음수로 만들기 위해 l을 증가시켜야 한다.
  • sum이 양수일 때에는, sum을 덜 양수로 만들기 위해 r을 감소시켜야 한다.
  • 어찌되었든 sum의 절댓값이 줄어들도록 그리디하게 움직이는 것이다.

• 이제 한 쪽 끝(i)을 고정하고, 나머지 두 쪽(l, r)을 투 포인터로 움직이면 된다.

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

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

const ll INF = numeric_limits<ll>::max();

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());

  if (arr[0] > 0) { // all acid
    cout << arr[0] << " " << arr[1] << " " << arr[2];
    return 0;
  }
  if (arr[n-1] < 0) { // all base
    cout << arr[n-3] << " " << arr[n-2] << " " << arr[n-1];
    return 0;
  }

  ll m = INF;
  array<int, 3> ans;
  for (int i=0;i<n-2;i++) {
    int l=i+1, r=n-1;
    while (l<r) {
      ll sum = arr[i]+arr[l]+arr[r];

      if (abs(sum) < m)
        m = abs(sum), ans = {i, l, r};

      if (sum > 0) {
        r--;
      } else if (sum < 0) {
        l++;
      } else {
        cout << arr[i] << " " << arr[l] << " " << arr[r];
        return 0;
      }
    }
  }
  cout << arr[ans[0]] << " " << arr[ans[1]] << " " << arr[ans[2]];

  return 0;
}