UCPC 2022 예선 D-20~D-17 문제풀이 일지

6월 12, 13, 14일을 설렁설렁 보내다가 15일이 되어 정신이 든 나...

늦었다고 생각할 때가 가장 빠른 때라고 하니 달려보겠습니다.

목차

1. 알고리즘 진도

- 2750번: 수 정렬하기

- 10815번: 숫자 카드

- 14425번: 문자열 집합

- 1269번: 대칭 차집합

- 11478번: 서로 다른 부분 문자열의 개수

- 3009번: 네 번째 점

- 2477번: 참외밭

- 3053번: 택시 기하학

- 1002번: 터렛

- 1004번: 어린 왕자

- 1358번: 하키

- 5086번: 배수와 약수

- 1037번: 약수

- 1934번: 최소공배수

- 2981번: 검문

- 3036번: 링

- 1010번: 다리 놓기

- 2004번: 조합 0의 개수

- 15651번: N과 M (3)

- 2580번: 스도쿠

- 14888번: 연산자 끼워넣기

- 14889번: 스타트와 링크

---

알고리즘 진도

최근 2주 정도 웹 개발하느라 알고리즘 문제풀이를 소홀히 했기 때문에 'BOJ 단계별로 풀어보기' 초반부의 풀지 않았던 문제를 풀어보면서 감을 되찾는 과정을 시행하기로 했습니다.

이에 따라 11일에 6~10단계를 완료했고, 이번에는 15단계 정도까지 완료할 생각으로 임했습니다.

※ C++ 코드 템플릿

혹시 제 코드를 참고하실 분들은 코드 최상단에 아래의 코드를 붙여넣어 주세요.

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define forn(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define all(v) (v).begin(), (v).end()

2750번: 수 정렬하기

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

2750번: 수 정렬하기

문제의 의도는 시간 복잡도가 O(n²)인 정렬 알고리즘로 풀어봐라! 인 것 같기에 내장 sort 함수를 쓰지 않고 풀어보기로 했습니다.

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

    int N;
    cin >> N;
    vector<int> A(N);
    forn(i, 0, N-1) cin >> A[i];

    forn(i, 0, N-1) {
        forn(i, 0, N-2) {
            if (A[i] > A[i+1]) swap(A[i], A[i+1]);
        }
    }

    forn(i, 0, N-1) cout << A[i] << "\n";

    return 0;
}

알고리즘 분류: 구현, 정렬

현 시점 난이도: 브론즈 II

10815번: 숫자 카드

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

10815번: 숫자 카드

쓰기 편한 ordered 자료구조(집합 등)를 사용하면 시간제한 안에 될 것 같습니다.

 

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

    int N;
    cin >> N;
    set<int> card; // an ordered set - insert O(logn)
    forn(i, 0, N-1) {
        int c;
        cin >> c;
        card.insert(c);
    }

    int M;
    cin >> M;
    forn(i, 0, M-1) {
        int q;
        cin >> q;
        if (card.find(q) != card.end()) // find O(logn)
            cout << "1 ";
        else
            cout << "0 ";
    }

    return 0;
}

알고리즘 분류: 자료 구조, 정렬, 이분 탐색

현 시점 난이도: 실버 V

14425번: 문자열 집합

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

14425번: 문자열 집합

역시 집합을 사용하는데, 문자열을 받아야 합니다.

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

    int N, M;
    cin >> N >> M;
    set<string> S;
    forn(i, 0, N-1) {
        string str;
        cin >> str;
        S.insert(str);
    }
    int ans = 0;
    forn(i, 0, M-1) {
        string q;
        cin >> q;
        if (S.find(q) != S.end()) ++ans;
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 자료 구조, 문자열, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

현 시점 난이도: 실버 III

1269번: 대칭 차집합

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

1269번: 대칭 차집합

Python에 대칭 차집합이 구현되어 있는 것을 알고 있어서, 이를 사용했습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

A = set(map(int, input().rstrip().split()))
B = set(map(int, input().rstrip().split()))
C = A.symmetric_difference(B)

print(len(C))

알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

현 시점 난이도: 실버 III

11478번: 서로 다른 부분 문자열의 개수

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

11478번: 서로 다른 부분 문자열의 개수

C++의 substr 또는 Python의 문자열 슬라이스, 그리고 집합 자료구조를 이용하면 간단합니다.

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

    string S;
    cin >> S;
    int N = S.size();
    set<string> substring;
    forn(i, 0, N-1) {
        forn(j, 1, N-i) {
            substring.insert(S.substr(i, j));
        }
    }
    cout << substring.size();

    return 0;
}

알고리즘 분류: 자료 구조, 문자열, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

현 시점 난이도: 실버 III

3009번: 네 번째 점

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

3009번: 네 번째 점

축에 평행한 직사각형이 문제의 조건이니까, x 방향과 y 방향 각각 두번씩 나온 숫자 하나와 한번 나온 숫자 하나가 있게 됩니다.

그러니 한 번만 나온 숫자를 출력하면 되겠죠.

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

    vector<int> X(3), Y(3);
    forn(i, 0, 2) cin >> X[i] >> Y[i];
    sort(all(X));
    sort(all(Y));
    if (X[0] == X[1]) cout << X[2] << " ";
    else cout << X[0] << " ";
    if (Y[0] == Y[1]) cout << Y[2];
    else cout << Y[0];

    return 0;
}

알고리즘 분류: 구현, 기하학

현 시점 난이도: 브론즈 III

2477번: 참외밭

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

2477번: 참외밭

올바른 방향만 찾으면 계산이 쉽지만, 그 방향을 찾는 것이 까다롭습니다.

저는 반시계방향으로 이동한다는 것에서 아이디어를 얻어, 예제 입력과 동일한 크기 순서가 아니라면 주어진 입력의 순서를 돌려버렸습니다.

이를 위해 벡터가 아닌 덱을 사용했구요.

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

    int K;
    cin >> K;
    deque<pii> L(6);
    forn(i, 0, 5) cin >> L[i].F >> L[i].S;
    while (L[0].S < L[2].S || L[0].S < L[4].S
        || L[1].S < L[3].S || L[1].S < L[5].S) {
        pii front = L[0];
        L.pop_front();
        L.PB(front);
    }
    cout << K * (L[0].S * L[1].S - L[3].S * L[4].S);

    return 0;
}

알고리즘 분류: 구현, 기하학

현 시점 난이도: 실버 III

3053번: 택시 기하학

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

3053번: 택시 기하학

C++에서 파이 상수는 M_PI를 사용하면 됩니다.

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

    int R;
    cin >> R;
    cout << fixed;
    cout.precision(6);
    cout << M_PI * R * R << "\n" << 2.00000000 * R * R;

    return 0;
}

알고리즘 분류: 수학, 기하학

현 시점 난이도: 브론즈 III

1002번: 터렛

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

1002번: 터렛

두 원의 교점의 개수를 구해야 하는데, 두 원의 중심 사이의 거리와 반지름 사이의 관계를 이용합니다.

경우의 수가 조금 많은 편입니다.

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

    int T;
    cin >> T;
    while (T--) {
        int x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        int cho_baik = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
        int ryu_plus = (r1 + r2) * (r1 + r2);
        int ryu_minus = (r1 - r2) * (r1 - r2);
        if (cho_baik == 0 && r1 == r2) cout << "-1\n";
        else if (cho_baik < ryu_minus) cout << "0\n";
        else if (cho_baik == ryu_minus) cout << "1\n";
        else if (cho_baik < ryu_plus) cout << "2\n";
        else if (cho_baik == ryu_plus) cout << "1\n";
        else cout << "0\n";
    }

    return 0;
}

알고리즘 분류: 수학, 기하학

현 시점 난이도: 실버 III

1004번: 어린 왕자

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

1004번: 어린 왕자

출발점과 도착점이 각 행성계 내부 또는 외부에 있는지를 조사해서 서로 반대쪽에 있으면 답에 1을 더하는 식으로 풀면 되겠습니다.

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

    int T;
    cin >> T;
    while (T--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int n;
        cin >> n;
        int ans = 0;
        forn(i, 0, n-1) {
            int cx, cy, r;
            cin >> cx >> cy >> r;
            int start_c = (cx - x1) * (cx - x1) + (cy - y1) * (cy - y1);
            bool is_start_in = start_c < r * r;
            int end_c = (cx - x2) * (cx - x2) + (cy - y2) * (cy - y2);
            bool is_end_in = end_c < r * r;
            if (is_start_in != is_end_in) ++ans;
        }
        cout << ans << "\n";
    }

    return 0;
}

알고리즘 분류: 기하학

현 시점 난이도: 실버 III

1358번: 하키

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

1358번: 하키

링크를 세 부분으로 나누고 각각에 대해 주어진 좌표를 포함하는지 계산하면 됩니다.

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

    int W, H, X, Y, P;
    cin >> W >> H >> X >> Y >> P;
    int ans = 0;
    forn(i, 1, P) {
        int x, y;
        cin >> x >> y;
        if (x >= X && x <= X + W && y >= Y && y <= Y + H) ++ans;
        else {
            bool left = (x - X) * (x - X) + (y - Y - H/2) * (y - Y - H/2) <= (H * H) / 4;
            bool right = (x - X - W) * (x - X - W) + (y - Y - H/2) * (y - Y - H/2) <= (H * H) / 4;
            if (left || right) ++ans;
        }
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 기하학

현 시점 난이도: 실버 IV

5086번: 배수와 약수

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

5086번: 배수와 약수

약수와 배수 관계 판정 문제!

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

    int A, B;
    cin >> A >> B;
    while (A || B) {
        if (A % B && !(B % A)) cout << "factor\n";
        else if (!(A % B) && B % A) cout << "multiple\n";
        else cout << "neither\n";
        cin >> A >> B;
    }

    return 0;
}

알고리즘 분류: 수학, 사칙연산

현 시점 난이도: 브론즈 III

1037번: 약수

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

1037번: 약수

자신과 1을 제외한 약수가 주어졌을 때, 수를 구하는 방법은...?

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

    int num;
    cin >> num;
    vector<int> fac(num);
    forn(i, 0, num-1) cin >> fac[i];
    sort(all(fac));
    cout << fac[0] * fac[num-1];

    return 0;
}

알고리즘 분류: 수학, 정수론

현 시점 난이도: 브론즈 I

1934번: 최소공배수

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

1934번: 최소공배수

최소공배수를 구하는 문제. 원래는 유클리드 호제법 등으로 약수를 다 구해야 하지만 lcm이라는 함수가 C++17에 있는데 굳이?

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

    int T;
    cin >> T;
    while (T--) {
        int A, B;
        cin >> A >> B;
        cout << lcm(A, B) << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 유클리드 호제법

현 시점 난이도: 브론즈 I

2981번: 검문

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

2981번: 검문

이 문제를 풀려면 첫째, 가능한 M들의 공통 성질을 알아야 하고, 둘째, 그 성질을 만족하는 수들을 빠르게 구하는 방법을 알아야 합니다.

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

    int N;
    cin >> N;
    vector<int> num(N);
    forn(i, 0, N-1) {
        cin >> num[i];
    }
    sort(all(num));
    int g;
    forn(i, 0, N-2) {
        if (i == 0) g = num[1] - num[0];
        else g = gcd(g, num[i+1] - num[0]);
    }
    vector<int> M;
    forn(i, 2, g) {
        if (i * i > g) break;
        if (g % i == 0) M.PB(i);
    }
    int n = M.size();
    forn(i, 1, n) if (M[n-i] * M[n-i] != g) M.PB(g / M[n-i]);
    M.PB(g);
    n = M.size();
    forn(i, 0, n-1) cout << M[i] << " ";

    return 0;
}

알고리즘 분류: 수학, 정수론, 유클리드 호제법

현 시점 난이도: 골드 IV

3036번: 링

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

3036번: 링

기약분수 꼴로 나타내야 한다는 조건이 있는 문제입니다. 분자와 분모의 최대공약수를 구해야겠죠.

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

    int N;
    cin >> N;
    int R;
    cin >> R;
    forn(i, 1, N-1) {
        int r;
        cin >> r;
        int g = gcd(r, R);
        cout << R / g << "/" << r / g << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 유클리드 호제법

현 시점 난이도: 실버 IV

1010번: 다리 놓기

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

1010번: 다리 놓기

M개 중 N개를 순서 없이 고르는 경우의 수를 구하는 문제죠.

이항 계수 구하는 과정은 입력이 작아 재귀로도 될 것 같지만, 동적 계획법을 써 보았습니다.

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

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<vector<int>> comb(M+1, vector<int>(M+1, 1));
        forn(i, 1, M) {
            forn(j, 1, i-1) {
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
            }
        }
        cout << comb[M][N] << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 다이나믹 프로그래밍, 조합론

현 시점 난이도: 실버 V

2004번: 조합 0의 개수

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

2004번: 조합 0의 개수

조합 계산 공식을 생각해 보면 팩토리얼에서 2와 5 인수의 개수를 3번씩 계산하면 됨을 알 수 있습니다.

int fac(int k, int l) {
    int ans = 0;
    while (k) {
        ans += k / l;
        k /= l;
    }
    return ans;
}

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

    int n, m;
    cin >> n >> m;
    int fives = fac(n, 5) - fac(m, 5) - fac(n-m, 5);
    int twos = fac(n, 2) - fac(m, 2) - fac(n-m, 2);
    cout << min(fives, twos);

    return 0;
}

알고리즘 분류: 수학, 정수론

현 시점 난이도: 실버 II

15651번: N과 M (3)

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

15651번: N과 M (3)

백트래킹 입문 문제 중 하나죠. N과 M 시리즈! 3번 문제의 경우는 숫자를 고르고 나서 골라진 여부를 bool로 저장할 필요가 없어서 체감 난이도가 낮습니다.

int N, M;
vector<int> seq;

void bt(int k) {
    if (k == M) {
        forn(i, 0, M-1) cout << seq[i] << " ";
        cout << "\n";
        return;
    }
    forn(i, 1, N) {
        seq.push_back(i);
        bt(k+1);
        seq.pop_back();
    }
}

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

    cin >> N >> M;
    bt(0);

    return 0;
}

알고리즘 분류: 백트래킹

현 시점 난이도: 실버 III

2580번: 스도쿠

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

2580번: 스도쿠

꽤 어려운 백트래킹 문제네요.

1. 백트래킹을 아무 순서로나 하면 시간 초과.

2. 숫자를 1부터 9까지 다 넣어보면서 올바른지 확인하면 시간 초과.

여기에 추가로 더 최적화가 필요할 수도 있을 것 같아요.

vector<vector<int>> board(9, vector<int>(9));
vector<pii> zero;
bool solved = false;

int valid_numbers(pii p) {
    // horizontal line
    int ans = (1 << 10) - 1;
    forn(i, 0, 8) {
        int num = board[p.F][i];
        ans &= ~(1 << num);
    }
    // vertical line
    forn(i, 0, 8) {
        int num = board[i][p.S];
        ans &= ~(1 << num);
    }
    // 3*3 box
    forn(i, 0, 2) {
        forn(j, 0, 2) {
            int num = board[p.F - p.F % 3 + i][p.S - p.S % 3 + j];
            ans &= ~(1 << num);
        }
    }
    return ans;
}

void solve(int k) {
    if (k == zero.size()) {
        forn(i, 0, 8) {
            forn(j, 0, 8) cout << board[i][j] << " ";
            cout << "\n";
        }
        solved = true;
        return;
    }
    int bitmask = valid_numbers(zero[k]);
    forn(n, 1, 9) {
        if (!(bitmask & (1 << n))) continue;
        board[zero[k].F][zero[k].S] = n;
        solve(k+1);
        if (solved) return;
        board[zero[k].F][zero[k].S] = 0;
    }
}

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

    forn(i, 0, 8) {
        forn(j, 0, 8) {
            int n;
            cin >> n;
            board[i][j] = n;
            if (n == 0) zero.PB(MP(i, j));
        }
    }
    solve(0);

    return 0;
}

알고리즘 분류: 백트래킹

현 시점 난이도: 골드 IV

14888번: 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

단계별로 풀어보기 내에서는 뒤에 배치되어 있지만, N-Queen이나 스도쿠 문제보다 확연히 쉬운 문제라고 할 수 있습니다,

int N;
vector<int> A, op, eq;
int mx = -1e9;
int mn = 1e9;

void solve(int k) {
    if (k == N-1) {
        int ans = A[0];
        forn(i, 0, N-2) {
            if (eq[i] == 0) ans += A[i+1];
            if (eq[i] == 1) ans -= A[i+1];
            if (eq[i] == 2) ans *= A[i+1];
            if (eq[i] == 3) ans /= A[i+1];
        }
        mx = max(mx, ans);
        mn = min(mn, ans);
        return;
    }
    forn(i, 0, 3) {
        if (op[i] == 0) continue;
        --op[i];
        eq.push_back(i);
        solve(k+1);
        ++op[i];
        eq.pop_back();
    }
}

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

    cin >> N;
    forn(i, 0, N-1) {
        int a;
        cin >> a;
        A.PB(a);
    }
    forn(i, 0, 3) {
        int o;
        cin >> o;
        op.PB(o);
    }
    solve(0);
    cout << mx << "\n" << mn;

    return 0;
}

알고리즘 분류: 브루트포스 알고리즘, 백트래킹

현 시점 난이도: 실버 I

14889번: 스타트와 링크

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

14889번: 스타트와 링크

스타트 팀과 링크 팀을 어떻게 반반씩 인원을 배정할지, 그리고 점수는 어떻게 매겨질지 생각해보면 풀리는 문제.

int N;
vector<vector<int>> S;
int team, chosen; // bitmask
int mn = 1e9;

void solve(int k) {
    if (k == N/2) {
        // construct both teams
        vector<int> start, link;
        forn(i, 0, N-1) {
            if (team & (1 << i)) start.PB(i);
            else link.PB(i);
        }
        // sum of start team
        int start_sum = 0;
        forn(i, 0, k-1) {
            forn(j, 0, k-1) {
                start_sum += S[start[i]][start[j]];
            }
        }
        // sum of link team
        int link_sum = 0;
        forn(i, 0, k-1) {
            forn(j, 0, k-1) {
                link_sum += S[link[i]][link[j]];
            }
        }
        mn = min(mn, abs(start_sum - link_sum));
        return;
    }
    forn(i, 0, N-1) {
        if (chosen & (1 << i)) continue;
        team |= (1 << i);
        forn(j, 0, i) chosen |= (1 << j);
        solve(k+1);
        team &= ~(1 << i);
        forn(j, i, N-1) chosen &= ~(1 << j);
    }
}

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

    cin >> N;
    forn(i, 0, N-1) {
        vector<int> v;
        S.PB(v);
        forn(j, 0, N-1) {
            int s;
            cin >> s;
            S[i].PB(s);
        }
    }
    solve(0);
    cout << mn;

    return 0;
}

알고리즘 분류: 브루트포스 알고리즘, 백트래킹

현 시점 난이도: 실버 II

BOJ 랜덤 디펜스

...는 내일부터 꼭 다시 하겠습니다!!

---

아 갈 길이 멀구나.