BOJ 11000 : 강의실 배정 (Gold 5)

• 와 를 한꺼번에 모은 뒤에 시간순으로 정렬하고 스택에 를 넣고 일때 pop하는 것을 반복한다.
• 이때 스택의 최대 크기가 강의실의 개수가 된다.
• 이렇게 구현하면 일 경우가 눈에 띈다. 이 경우 스택의 최대 크기를 pop할 때 세되, 와 의 값이 같을 경우 세지 않으면 된다.
  • 시간이 같을 때 가 먼저 등장하고 가 나중에 등장해야 스택을 유지할 수 있는데 우연히도 S가 T보다 앞서있다. 오예!

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

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

  int N; cin >> N;
  vector<pair<int, char>> v; v.reserve(2*N);

  for (int i=0;i<N;i++) {
    int s, t; cin >> s >> t;
    v.emplace_back(s, 'S');
    v.emplace_back(t, 'T');
  }

  sort(v.begin(), v.end()); // 'S' < 'T'

  stack<int> s;
  int mm = -1;
  for (int i=0;i<2*N;i++) {
    auto [pos, st] = v[i];
    if (st == 'S') {
      s.push(pos);
    } else {
      if (s.top() != pos) {
        mm = max(mm, (int) s.size());
      }
      s.pop();
    }
  }

  cout << mm;

  return 0;
}

BOJ 1107 : 리모컨 (Gold 5)

• 남은 버튼으로 reachable한 채널 번호를 bitset에 저장하고 으로부터 왼쪽 오른쪽을 넓혀가면서 검사해서 (숫자자릿수) + (+- 개수)로 답을 내면 된다.
• 시작 채널인 100번에서 +-하는게 효율적이면 그걸 따른다.
• 밑의 코드의 d가 같을 때 자릿수가 차이날 수 있기에 왼쪽이 우선이라는 점을 고려하지 못했다.

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

typedef vector<int> vi;

bitset<1000001> dp;
bool digit[10];
void dfs(int i) {
  for (int j=0;j<=9;j++) {
    if (!digit[j]) continue;

    if (i*10+j <= 1000000) {
      dp[i*10+j] = true;
      if (i > 0 || j > 0) dfs(i*10+j);
    }
  }
}

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

  int N, M; cin >> N >> M;

  memset(digit, true, 10);
  for (int i=0;i<M;i++) {
    int x; cin >> x;
    digit[x] = false;
  }

  dfs(0);

  int num = -1, d;
  for (d=0;d<=500000;d++) {
    if (N-d>=0 && dp[N-d]) { // smaller one first
      num = N-d;
      break;
    }
    if (N+d<=1000000 && dp[N+d]) {
      num = N+d;
      break;
    }
  }

  if (num == -1) { // no num button
    cout << abs(N-100);
  } else {
    cout << min((int) log10(max(num, 1)) + d + 1, abs(N-100));
  }

  return 0;
}

BOJ 1197 : 최소 스패닝 트리 (Gold 4)

• MST를 구하는 문제다. Prim’s Algorithm으로 구현했다.

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

typedef pair<int, int> pii;

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

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

  int V, E; cin >> V >> E;
  vector<vector<pii>> G(V+1);
  vector<int> key(V+1, INF);
  vector<bool> visited(V+1, false);

  for (int i=0;i<E;i++) {
    int a, b, w; cin >> a >> b >> w;
    G[a].emplace_back(w, b);
    G[b].emplace_back(w, a);
  }

  priority_queue<pii, vector<pii>, greater<>> pq;
  pq.emplace(0, 1);
  key[1] = 0;
  while (!pq.empty()) {
    int u = pq.top().second; pq.pop();
    visited[u] = true;

    for (auto [w, v] : G[u]) {
      if (!visited[v] && w < key[v]) {
        key[v] = w;
        pq.emplace(w, v);
      }
    }
  }

  cout << accumulate(key.begin()+1, key.end(), 0);

  return 0;
}

BOJ 33466 : 피타고라스 정리의 증명 (Gold 5)

• 에서 가 양의 정수가 되도록 하는 순서쌍 ()의 개수를 구하는 문제이다.

• 식을 정리하면,

• 가 유리수이므로, 은 완전제곱수이다.

• 이라고 하고, 일반성을 잃지 않고 은 음이 아닌 정수라고 하자.

• 의 범위는 이다.

  • 수열 ()과 이 수열의 차이 ()을 생각하자.
  • 인데, 와 의 차이인 16은 와 의 사이에 있다.
  • 이상의 을 에 더해서 인접한 를 만들 수 없다.
  • 모든 양의 정수 에 대해 이므로 는 와 인접하지 않더라도 만들어질 수 없다.

• 이제 가능한 에 대해 이 완전제곱수가 되는지 확인해주면 된다.

  	0	1	2	3	4	5	6	7
  	16	17	20	25	32	41	52	65
  가 완전제곱수?	O	X	X	O	X	X	X	X

• 이므로 이다.¹

• 이제 각 경우에 대해 개수를 세면 된다.

  1. 인 경우 순서쌍 의 개수는 개이다.
  2. 인 경우 순서쌍 의 개수는 개이다.
  3. 인 경우는 2와 같다.

• 따라서 각 케이스에 대해 를 출력해주면 된다.

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

typedef long long ll;

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

  int t; cin >> t;
  while (t--) {
    ll n; cin >> n;
    cout << (n*2 - n%2) << '\n';
  }

  return 0;
}

BOJ 9663 : N-Queen (Gold 4)

• 웰 노운이지만 꽤 어렵다고 생각한다.
• 2차원 백트래킹으로 꾸역꾸역 풀고 싶어서 그렇게 했다.

#include <bits/stdc++.h>

using namespace std;

int visited[15][15] = {0, };
int cnt;
int n;

void update(int qx, int qy, int d) {
  visited[qx][qy] += d;
  for (int i=0;i<n;i++) {
    if (i != qx)
      visited[i][qy] += d;
    if (i != qy)
      visited[qx][i] += d;
    if (i != qx && 0<=qy-qx+i && qy-qx+i<n)
      visited[i][qy-qx+i] += d;
    if (i != qx && 0<=qy+qx-i && qy+qx-i<n)
      visited[i][qy+qx-i] += d;
  }
}

void dfs(int qx) { // qx == queen count
  if (qx == n) {
    cnt++;
    return;
  }
  for (int j = 0; j < n; j++) {
    if (visited[qx][j] > 0) continue;

    update(qx, j, +1);
    dfs(qx+1);
    update(qx, j, -1);
  }
}

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

  cin >> n;
  memset(visited, 0, 15 * 15 * sizeof(int));
  dfs(0);
  cout << cnt;

  return 0;
}

BOJ 1034 : 램프 (Gold 4)

• 스위치를 누르는 위치 및 횟수가 모두 켤 수 있는 행패턴이 일대일로 대응된다는 것을 알면 쉽다.
• std::popcount는 C++20부터 지원된다는 사실...

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

typedef long long ll;

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

  int N, M; cin >> N >> M;
  map<ll, int> m;
  for (int i=0;i<N;i++) {
    string s; cin >> s;
    ll x = stoll(s, nullptr, 2);
    m[x]++;
  }
  int K; cin >> K;

  int mm = 0;
  for (auto [pat, cnt] : m) {
    int zero_count = M - __builtin_popcountll(pat);
    if (K >= zero_count && (K - zero_count) % 2 == 0)
      mm = max(mm, cnt);
  }

  cout << mm;

  return 0;
}

BOJ 9935 : 문자열 폭발 (Gold 4)

• 너무 어렵게 푼 것 같다.

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

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

  string haystack, needle;
  cin >> haystack >> needle;

  int state = 0;
  vector<int> v;
  string result;
  for (int i=0;i<haystack.length();i++) {
    if (haystack[i] == needle[0]) {
      if (state > 0) v.push_back(state);
      state = 1;

      if (needle.size() == 1) {
        if (v.empty())
          state = 0;
        else
          state = v.back(), v.pop_back();
      }
      continue;
    }
    bool found = false;
    for (int j=1;j<needle.size();j++) {
      if (state == j && haystack[i] == needle[j]) {
        state++;
        if (state == needle.size()) {
          if (v.empty())
            state = 0;
          else
            state = v.back(), v.pop_back();
        }
        found = true;
      }
    }
    if (!found) {
      v.push_back(state);
      for (int s : v)
        for (int j=0;j<s;j++)
          result.push_back(needle[j]);
      result.push_back(haystack[i]);
      v.clear();
      state = 0;
    }
  }
  v.push_back(state);
  for (int s : v)
    for (int j=0;j<s;j++)
      result.push_back(needle[j]);

  cout << (result.empty() ? "FRULA" : result);

  return 0;
}

• 찾아보니 needle과 haystack[i-m+1..i]을 비교해서 일치하면 needle의 길이만큼 지금까지 쌓아온 문자열에서 삭제하면 되는 것이었다. 그럼 대충 이었다.

  #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  
    string s, bomb;
    cin >> s >> bomb;
    string ans;
    int bombSize = bomb.size();
  
    for (char c : s) {
      ans.push_back(c);
      if (ans.size() >= bombSize && ans.substr(ans.size() - bombSize) == bomb)
        ans.erase(ans.size() - bombSize);
    }
  
    cout << (ans.empty() ? "FRULA" : ans);
    return 0;
  }
  

BOJ 2293 : 동전 (Gold 4)

• 예제를 바탕으로 bottom-up으로 DP할 방법을 궁리했다.
• 정렬은 안해도 되나보다.

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

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

  int n, k; cin >> n >> k;
  vector<int> dp(k+1, 0);
  vector<int> v(n);

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

  sort(v.begin(), v.end());

  dp[0] = 1;
  for (int i=0;i<n;i++)
    for (int j=1;j<=k;j++)
      if (j-v[i]>=0)
        dp[j] += dp[j-v[i]];

  cout << dp[k];

  return 0;
}