Problem Solving @ 2022/04/18

1. Cow Contest (G4) - From. USACO January 2008 Contest Silver 1번

 

시간 복잡도: O(N^2)

알고리즘: DFS

 

그래프 문제입니다. 순위를 특정하려면, 앞에 있다고 확신할 수 있는 소의 수와 뒤에 있다고 확신할 수 있는 소의 수가 전체 소의 수에서 1을 뺀 값이 되어야 합니다.

 

예를 들어, { (1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (6, 4), (6, 1) } 의 입력이 주어졌을 때, node 번호를 가진 소 뒤에 있는 소들의 관계는 다음과 같습니다:

 

뒤

 

여기서 node 번호가 붙은 소 뒤에 있는 소의 수는 dfs를 통해 쉽게 구현할 수 있습니다.

또한, 앞에 있는 소들의 관계는 간선의 방향을 뒤집어 다시 dfs로 탐색합니다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> graph[101][2];
bool chk[101][2];

int dfs(int idx, int oper) {

  if (chk[idx][oper]) return 0;
  chk[idx][oper] = true;

  int nodes = 0;
  for (int i = 0; i < graph[idx][oper].size(); i++) {
    int nxt = graph[idx][oper][i];
    nodes += dfs(nxt, oper);
  }

  return nodes + 1;
}

int main() {

  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int from, to; cin >> from >> to;
    graph[from][0].push_back(to);
    graph[to][1].push_back(from);
  }

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) { chk[j][0] = false; chk[j][1] = false; }
    if (dfs(i, 1) + dfs(i, 0) - 2 == N - 1) ans++;
  }

  cout << ans << endl;
}

 

 

2. 인터넷 설치 (G1) - From. USACO January 2008 Contest Silver 3번

 

시간 복잡도: O(ElogVlogL)

알고리즘: 이분 탐색, 다익스트라

 

이 문제는 연결된 간선 중 최댓값을 지불하는 문제입니다.

"r 이하의 비용을 사용하여 1~N까지 이을 수 있는가?" 와 같은 P 문제로 변환해서 생각해봅시다.

이때 r 이하의 비용을 들이려면, r 이상의 비용을 가는 길에 K번 이상 포함시키면 해는 성립되지 않습니다; 이때 r 이상의 비용을 최대한 포함하지 않는 길은 일반적인 최단거리 알고리즘, 다익스트라를 써서 쉽게 구할 수 있습니다.

 

이렇게 P 문제로 나타냈다고 칩시다; 그런데 시간 복잡도는 어떻게 더 줄일까요?

r 이하의 값으로 비용을 낼 수 있다면, r+1 이하의 값으로 비용을 낼 수 있으므로, 이분 탐색을 이용해 log시간 안에 해결할 수 있습니다:

 

 

• 1. 조건이 성립한다면, right = mid, update answer.
• 2. 아니면, left = mid

 

와 같은 방법으로 풀이할 수 있습니다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define pp pair<int, int>

int N, P, K;
vector<pp> graph[1001];

bool djikstra(int oper) {

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

  priority_queue<pp, vector<pp>, greater<pp> > pq;
  pq.push({0, 1}); // cost, idx

  while (!pq.empty()) {

    int idx = pq.top().second;
    int cost = pq.top().first;
    pq.pop();

    if (D[idx] < cost) continue;

    for (int i = 0; i < graph[idx].size(); i++) {
      int nxt = graph[idx][i].first;
      int dist = (graph[idx][i].second > oper) + cost;

      if (D[nxt] > dist) {
        D[nxt] = dist;
        pq.push({dist, nxt});
      }
    }
  }

  /*
  cout << oper << ": ";
  for (int i = 1; i <= N; i++) {
    cout << D[i] << ", ";
  }
  cout << endl;
  */

  return !(D[N] - K > 0);
}

int main() {

  cin >> N >> P >> K;
  for (int i = 0; i < P; i++) {
    int from, to, cost; cin >> from >> to >> cost;
    graph[from].push_back({to, cost});
    graph[to].push_back({from, cost});
  }

  // 최댓값이 mid가 되게 만들 수 있나?
  // 1. x가 가능하다면 x보다 작은 해에서도 무조건 성립
  // 2. x가 가능하고 x + 1이 불가능하다면 -> x가 답
  // 3. x가 최댓값이 된다 -> 1와 N을 잇는 거리에 x보다 큰 값이 K번 이상 있으면 안 됨.
  int l = 0, r = 1000000, ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (djikstra(mid)) {
      ans = mid;
      r = mid - 1;
    }
    else l = mid + 1;
  }

  cout << ans << endl;
}

 

 

3. Berry Picking (G2) - From. USACO 2020 January Contest Silver 1번

 

시간 복잡도: O(N^2)

알고리즘: 그리디, 우선순위 큐, 브루트포스

 

K는 항상 짝수입니다. (테스트 해봄.) Bessie가 가질 수 있는 최댓값을 x라 합시다. x보다 큰 인덱스에 대해 x 이상의 값을 Elsie의 바구니에 넣는 것은 손해입니다. 따라서, Elsie의 바구니엔 모두 x가 있어야 합니다.

 

우리는 이러한 알고리즘을 생각해 볼 수 있습니다: x보다 큰 인덱스의 값을 모두 x값 y개로 + a 로 나타냅니다.

a는 임의의 우선순위 큐에 넣습니다.

예를 들어, tree[i] = 8 이고, x = 3일 때, tree[i]를 { 3, 3, 2 } 로 나타내라는 말입니다. x의 개수를 r이라 하겠습니다.

이때, Elsie가 가지는 x의 개수, K/2개를 r에서 빼고, 이제 Bessie의 바구니에 r개의 x을 더하고, Bessie의 바구니가 K-r개가 될 때까지, 우선순위 큐에서 원소를 빼내며 더합니다.

 

x = 1부터 tree[i]의 최댓값까지 반복합니다;

위에서 설명한 알고리즘으로 답을 업데이트합니다. x의 개수가 K/2를 넘지 않는다면, "Bessie가 가질 수 있는 최댓값은 x" 에 부흥하지 않으므로, 반복문을 종료합니다. (x+1의 값 또한 K/2개를 넘지 않는다는 것은 자명한 사실입니다.)

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int N, K;
int trees[1001];

int main() {

  cin >> N >> K;

  int maxi = -1;
  for (int i = 1; i <= N; i++) {
    cin >> trees[i];
    maxi = max(trees[i], maxi);
  }

  int ans = -1;
  for (int i = 1; i <= maxi; i++) {

    priority_queue<int> pq;
    int r = 0;
    for (int j = 1; j <= N; j++) {
      r += trees[j] / i;
      if (trees[j] % i != 0) pq.push(trees[j] % i);
    }

    if (r <= K / 2) break;
    if (r >= K) ans = max(i * (K / 2), ans);
    else {
      r -= (K / 2);
      int cnt = r, sum = r * i;

      while (!pq.empty() && cnt < K / 2) {
        cnt++; sum += pq.top();
        pq.pop();
      }

      if (cnt < K / 2) continue;
      ans = max(sum, ans);
    }
  }

  cout << ans << endl;
}