[SPC 풀이]2018 Sogang Programming Contest - Master

A. 3의 배수

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

16561번: 3의 배수

- 3000 이하의 3의 배수가 주어지면 이 수를 3의 배수인 자연수 3개의 합으로 만들 수 있는 경우의 수 를 구한다.

- 즉, A + B + C = N (A = 3a, B = 3b, C = 3b, N = 3n) 를 만족하는 자연수 A, B, C의 경우의 수를 구한다.

- 양변을 3으로 나누면 a + b + c = n 이고, a, b, c는 최소 1로 각각 1씩 부여하고 남은 n-3을 a, b, c에게 나눠준다.

=> $ _{3}H_{n-3} = _{n-1}C_{n-3} = \frac{(n-1)(n-2)}{2}$ 를 구하면 된다.

// BOJ 16561 3의 배수

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n < 9) 
        cout << 0;
    else {
        n = (n - 9) / 3 + 3 - 1;
        cout << n * (n - 1) / 2;
    }
}

 

B. 친구비

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

16562번: 친구비

- 준석이는 n명의 학생과 친구가 되고 싶고 각 학생은 친구비를 내면 친구가 될 수 있다. 친구의 친구도 친구다

- 즉, 준석이가 친구 그룹의 한 학생과 친구가 되면 해당 그룹의 학생은 모두 준석이의 친구가 된다.

- 그룹 간의 merge가 되므로 Disjoint set으로 풀면 된다. 준석이를 0번 학생으로 생각하자.

- 친구비를 최소로 쓰고 싶기 때문에 친구비가 싼 학생부터 친구가 된다.

// BOJ 16562 친구비
// Disjoint set Union

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define BtoE(vec) vec.begin(), vec.end()
#define Pii pair<int, int>

int n, m, k, par[10001];
vector<Pii> cost;

int find(int i) {
    if (par[i] < 0) return i;
    return par[i] = find(par[i]);
}
bool merge(int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return false;
    par[j] = i;
    return true;
}

int main() {
    cin >> n >> m >> k;

    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c;
        cost.push_back(Pii(c, i + 1));
    }
    sort(BtoE(cost));

    fill(par, par + 10001, -1);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }

    int money = 0;
    for (int i = 0; i < n; ++i) {
        if (merge(0, cost[i].second)) {
            money += cost[i].first;
        }
    }

    if (money > k) cout << "Oh no";
    else cout << money;
}

 

3. 어려운 소인수분해

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

16563번: 어려운 소인수분해

- 소인수분해를 하려면 우선 소수 판별을 해야한다.

- 소수 판별에는 에라토스테네스의 체를 이용한다.

- 처음엔 소수 판별을 bool타입의 배열에 체크만 한 후, 소수를 따로 모아놓고 K를 가장 작은 소수 약수로 다 나눌 때까지 나눠줬다.

- 에라토스테네스의 체를 살짝 변형시켜서 int타입의 배열에 n이 소수면 0을,  아니면 가장 작은 소수 약수를 기록해서 가장 작은 소수 약수를 따로 찾지 않아도 O(1)에 알 수 있도록 한다.

// BOJ 16563 어려운 소인수분해
// Eratosthenes sieve

#include <iostream>
using namespace std;
#define ll    long long

int minp[5000001];
void era() {
    for (ll i = 2; i <= 5000000; ++i) {
        if (minp[i]) continue;
        for (ll j = i; i * j <= 5000000; ++j) {
            if (minp[i * j]) continue;
            minp[i * j] = i;
        }
    }
}

int main() {

    era();

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        while (minp[x]) {
            cout << minp[x] << ' ';
            x /= minp[x];
        }

        cout << x << '\n';
    }
}

 

4. 히오스 프로게이머

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

16564번: 히오스 프로게이머

- 캐릭터의 수 n과 레벨 포인트 k가 주어지고 각 캐릭터의 현재 레벨이 주어진다.

- 레벨 포인트를 적절히 분배해서 캐릭터들 중 최소 레벨이 최대로 높아지게 만든다.

- 이분탐색을 이용해서 조건을 충족하는 최대 레벨을 구하면 된다.

- 하지만 이분탐색 안하고 그냥 낮은 레벨부터 차근차근 올려줘도 문제가 안된다. pq를 이용했다.

- minlev은 현재 가장 낮은 레벨, minc는 현재 레벨이 minlev인 캐릭터의 수

// BOJ 16564 히오스 프로게이머
// heap

#include <iostream>
#include <queue>
using namespace std;
#define ll    long long

int main() {
    ll n, k;
    priority_queue<ll, vector<ll>, greater<ll> > pq;

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        pq.push(x);
    }

    ll minlev = pq.top(), minc = 1;
    pq.pop();
    while (1) {
        while (!pq.empty() && minlev == pq.top()) {
            pq.pop();
            minc++;
        }
        if (pq.empty()) break;

        ll diff = pq.top() - minlev;
        if (k - diff * minc <= 0) {
            minlev += k / minc;
            k = 0;
            break;
        }
        else {
            minlev += diff;
            k -= diff * minc;
        }
    }
    minlev += k / n;

    cout << minlev;
}

 

5. N포커

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

16565번: N포커

- 52장의 트럼프 카드 세트에서 n장의 카드를 뽑아서 최소 하나의 포카드를 만들어내는 경우의 수를 구한다

- 포카드는 총 13세트가 있다.

- n장을 뽑을 때, 포카드를 i개 생성하는 경우의 수는 $_{13}C_{i}$ 이고 이 때, 4i 개의 카드를 뽑은 상태에서 남은 카드를 뽑는 경우는 $_{52-4i}C_{n-4i}$ 이다. 즉, n장을 뽑을 때, 포카드가 i개 생성되는 경우의 수는 다음과 같다.

$$_{13}C_{i} X _{52-4i}C_{n-4i}$$

 

- 과연 맞을까?

- 아니다. $_{52-4i}C_{n-4i}$ 에서도 포카드가 생길 수 있다.

- 그렇다면 중복되는 경우를 빼주면 되겠다. 집합에서 합집합의 원소의 개수를 생각하자.

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

$$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(B \cap C) - n(C \cap A) + n(A \cap B \cap C)$$

- 대충 이런 느낌으로 하면 된다.

- 조합은 미리 전처리로 구해놓으면 된다. 나머지 모듈로 처리도 알아서 잘하자

// BOJ 16565 N포커
// combination & Dynamic programming

#include <iostream>
using namespace std;

const int mod = 10007
int n, bino[53][53];

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

    int res = 0;

    for (int i = 0; i <= 52; ++i) {
        bino[i][0] = bino[i][i] = 1;
        for (int j = 1; j < i; ++j)
            bino[i][j] = (bino[i - 1][j - 1] + bino[i - 1][j]) % mod;
    }

    cin >> n;
    for (int i = 4; i <= n; i += 4) {
        res = (res + ((i / 4) % 2 ? 1 : -1) * bino[13][i / 4] * bino[52 - i][n - i]) % mod;
    }
    if (res < 0) res += mod;

    cout << res;
}

 

6. 카드 게임

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

16566번: 카드 게임

- 6번 작성한 글이 한 번 지워졌다;;;;;;;;;;;;;;;

- 1~n 의 카드가 있다.

- 마술사 철수는 내고싶은 걸 맘대로 낸다.

- 심리술사 민수는 m장의 카드를 골라서 많아도 1번 밖에 못내지만 철수가 뭘 낼지 다 알고 있다.

- 문제에서 말하길 "철수가 낼 카드보다 큰 카드가 있으면 그 카드들 중 가장 작은 카드"를 낸다.

- 답이 나왔네요. upper_bound를 쓰라고 대놓고 말하고 있다.

- 대신 민수는 한 카드를 한 번 밖에 못내므로 check 배열을 이용해서 upper_bound를 이용해 찾고 아직 내지 않은 카드로 올라간다.

// BOJ 16566 카드 게임
// Binary search

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define BtoE(vec) vec.begin(), vec.end()

int n, m, k, chulsu[10000];
vector<int> minsu;
vector<bool> checked;

int main() {
    cin >> n >> m >> k;

    minsu.resize(m);
    checked.resize(m, false);
    for (int i = 0; i < m; ++i) cin >> minsu[i];
    sort(BtoE(minsu));
    for (int i = 0; i < k; ++i) cin >> chulsu[i];

    for (int i = 0; i < k; ++i) {
        int minsu_idx = upper_bound(BtoE(minsu), chulsu[i]) - minsu.begin();
        while (checked[minsu_idx]) minsu_idx++;

        checked[minsu_idx] = true;
        cout << minsu[minsu_idx] << '\n';
    }
}