UCPC 2022 예선 D-21 문제풀이 일지

블로그 업데이트는 오랜만입니다.

지난 두 달 동안은 공부한 내용을 굳이 공개된 곳에 전부 깔끔히 정리해 포스팅할 필요는 없지 않을까~라는 생각에 개인 GoodNotes 계정에만 정리해두고 있었습니다. 굿노트가 워낙 효율이 좋아서인지 기존보다 훨씬 많은 공부량을 뽑아낼 수 있었지만, 최근 며칠 동안은 공부할 의욕이 잘 나지 않아 고민하던 차에 업데이트가 뜸하던 블로그가 생각났습니다.

UCPC 2022에 출전하게 됨에 따라 예선(그리고 잘 되면 본선까지..)을 대비해 매일 일정 수의 문제를 풀어보려고 하는데, 푼 문제를 블로그에 일지 형식으로 정리해보면 좋겠다고 판단해서 글을 작성하기 시작했습니다.

목차

1. 오늘의 알고리즘 진도

- 2941번: 크로아티아 알파벳

- 1193번: 분수찾기

- 10757번: 큰 수 A+B

- 2581번: 소수

- 11653번: 소인수분해

- 4948번: 베르트랑 공준

- 9020번: 골드바흐의 추측

- 10870번: 피보나치 수 5

- 17478번: 재귀함수가 뭔가요?

2. BOJ 랜덤 디펜스

- 1645번: 성지의 생일파티

- 10332번: Shopping

- 6161번: iCow

- 9693번: 시파르

---

오늘의 알고리즘 진도

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

이에 따라 어제는 1~5단계를 완료했고, 오늘은 10단계 정도까지 완료할 생각으로 임했습니다.

※ C++ 코드 템플릿

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

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <utility>
#include <tuple>
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()

2941번: 크로아티아 알파벳

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

2941번: 크로아티아 알파벳

처리해야 할 것이 8가지밖에 되지 않으니 무지성 if 문으로 구현할 수 있을 듯한 문제입니다. 주어진 문자열을 순회하면서 하나씩 세되 크로아티아 알파벳이 나온다면 그 길이만큼 건너뛰면 되겠죠.

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

    string s;
    cin >> s;

    int n = s.size();
    int ans = 0;
    forn(i, 0, n-1) {
        ++ans;
        if (i == n-1) break;
        if (s[i] == 'c') {
            if (s[i+1] == '=' || s[i+1] == '-') ++i;
        }
        else if (s[i] == 'd') {
            if (s[i+1] == '-') ++i;
            else if (i+2 < n && s[i+1] == 'z' && s[i+2] == '=') i += 2;
        }
        else if (s[i] == 'l' && s[i+1] == 'j') ++i;
        else if (s[i] == 'n' && s[i+1] == 'j') ++i;
        else if (s[i] == 's' && s[i+1] == '=') ++i;
        else if (s[i] == 'z' && s[i+1] == '=') ++i; 
    }

    cout << ans;

    return 0;
}

알고리즘 분류: 구현, 문자열

현 시점 난이도: 실버 V

1193번: 분수찾기

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

1193번: 분수찾기

X번째 분수가 몇 번째 대각선에 있는지 어떻게 알까요?

저는 떠오르는 방법이 마땅치 않아서 이분탐색을 쓰고 구현하느라 좀 고생했는데 인터넷 검색을 해 보니 그냥 1, 2, 3, ...을 순차적으로 X에서 빼면 되더라구요.

그 방법을 아니까 구현이 매우 쉬울 것 같다는 생각이 드네요...

아래 코드는 이분탐색을 사용한 코드인데 이렇게 하지는 마세요!

int X;

bool valid(int n) {
    int R = n * (n + 1) / 2;
    if (X <= R) return true;
    else return false;
}

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

    cin >> X;

    int l = 1, r = (int)sqrt(2 * X);
    while (l <= r) {
        int m = (l + r) / 2;
        if (valid(m)) r = m - 1;
        else l = m + 1;
    }

    int s = l * (l + 1) / 2;
    int p = s - X + 1;
    int q = l + 1 - p;

    if (l % 2) cout << p << "/" << q;
    else cout << q << "/" << p;

    return 0;
}

알고리즘 분류: 수학, 구현

현 시점 난이도: 브론즈 I

10757번: 큰 수 A + B

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

10757번: 큰 수 A+B

이 문제는 C/C++로 풀기가 상대적으로 어렵습니다. 무지성 A+B가 안 되기 때문이죠!
저는 문자열로 큰 수를 받아서 받아올림을 구현하는 방식으로 풀었습니다.

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

    string A, B;
    cin >> A >> B;

    int n = max(A.size(), B.size());
    while (A.size() < n) A = '0' + A;
    while (B.size() < n) B = '0' + B;

    string C = "";
    int sum = 0, up = 0;
    forn(i, 1, n) {
        int ai = A[n-i] - '0';
        int bi = B[n-i] - '0';
        sum = ai + bi + up;
        if (sum > 9) {
            sum -= 10;
            up = 1;
        } else up = 0;
        C = (char)('0' + sum) + C;
    }
    if (up == 1) C = '1' + C;

    cout << C;

    return 0;
}

알고리즘 분류: 수학, 구현, 사칙연산, 임의 정밀도 / 큰 수 연산

현 시점 난이도: 브론즈 V (특정 언어에서 매우 쉬워서 그렇습니다.)

2581번: 소수

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

2581번: 소수

입력이 그다지 크지 않기 때문에 2부터 x-1까지 전부 나눠보는 기본적인 소수 판정법만으로 충분합니다.

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

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

    int sum = 0;
    int mn = N+1;
    forn(i, M, N) {
        bool is_prime = true;
        if (i == 1) is_prime = false;
        forn(j, 2, i-1) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            sum += i;
            mn = min(mn, i);
        }
    }

    if (sum == 0) cout << -1;
    else cout << sum << "\n" << mn;

    return 0;
}

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

현 시점 난이도: 실버 V

11653번: 소인수분해

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

11653번: 소인수분해

모든 수로 나눠보면서 찾으려고 하면 시간 초과가 발생합니다. 시간 안에 동작하려면 다음과 같은 최적화가 필요합니다.

1. 소수를 찾으면, 소수 배열에 넣어서 다음으로 큰 소수를 찾는 시간을 줄인다.

2. 소수를 찾을 때, 소수 배열 중에서 판정하려는 수의 제곱근 이하의 값만 보면 된다.

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

    int N;
    cin >> N;

    vector<int> primes;
    forn(i, 2, N) {
        bool is_prime = true;
        for (auto j : primes) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
            if (j * j > i) break;
        }
        if (is_prime) {
            primes.PB(i);
            while (N % i == 0) {
                cout << i << "\n";
                N /= i;
            }
        }
    }

    return 0;
}

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

현 시점 난이도: 실버 V

4948번: 베르트랑 공준

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

4948번: 베르트랑 공준

소인수분해 문제에서 사용한 방법을 여러 개의 테스트 케이스에 대해서 반복하면 됩니다.

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

    int n;
    cin >> n;

    while (n > 0) {
        
        vector<int> primes;
        int ans = 0;
        forn(i, 2, 2 * n) {
            bool is_prime = true;
            for (auto p : primes) {
                if (p * p > i) break;
                if (i % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                primes.PB(i);
                if (i > n) ++ans;
            }
        }

        cout << ans << "\n";
        cin >> n;
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

현 시점 난이도: 실버 II

9020번: 골드바흐의 추측

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

9020번: 골드바흐의 추측

소인수분해 문제에서 사용한 방법을 응용한 또 다른 문제입니다.

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

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> primes;
        // find primes below n / 2
        forn(i, 2, n / 2) {
            bool is_prime = true;
            for (auto p : primes) {
                if (p * p > i) break;
                if (i % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                primes.PB(i);
            }
        }
        // iterate from biggest prime
        // if n - prime is also prime, print the answer
        int cnt = primes.size();
        forn(i, 1, cnt) {
            int num = n - primes[cnt - i];
            bool is_prime = true;
            for (auto p : primes) {
                if (p * p > num) break;
                if (num % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                cout << primes[cnt - i] << " " << num << "\n";
                break;
            }
        }
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

현 시점 난이도: 실버 II

10870번: 피보나치 수 5

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

10870번: 피보나치 수 5

입력 제한이 너무 시시하지만... 재귀로 풀어 봅시다.

int fib(int n) {
    if (n <= 0) return 0;
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

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

    int n;
    cin >> n;

    cout << fib(n);

    return 0;
}

알고리즘 분류: 구현, 수학, 재귀

현 시점 난이도: 브론즈 V

17478번: 재귀함수가 뭔가요?

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

17478번: 재귀함수가 뭔가요?

재귀에 대한 연습이 확실히 되는 문제지만 구현이 귀찮아요!

int n;

string rec(int k) {
    string under = "";
    forn(i, 1, k) {
        under += "____";
    }
    if (k == n) {
        string r = under + "\"재귀함수가 뭔가요?\"\n";
        r += under + "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
        r += under + "라고 답변하였지.\n";
        return r;
    }
    string r = "";
    r += under + "\"재귀함수가 뭔가요?\"\n";
    r += under + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
    r += under + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
    r += under + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
    r += rec(k + 1);
    r += under + "라고 답변하였지.\n";
    return r;
}

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

    cin >> n;

    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
    cout << rec(0);

    return 0;
}

알고리즘 분류: 구현, 재귀

현 시점 난이도: 실버 V

BOJ 랜덤 디펜스

쉬운 문제를 빠르게 푸는 연습을 위해 BOJ 랜덤 디펜스를 하기로 했습니다.

사용한 solved.ac 명령어는 ( lang:ko | lang:en ) & *b5..s1 - @$me 이며, 제가 풀지 않은 문제 중 한국어 또는 영어로 된 브론즈 또는 실버 문제를 검색하고 랜덤 4문제를 풀기로 하였습니다. 그리고 4문제 중 1문제 이상을 Python으로 풀기로 했습니다.

저는 현재 골드 I 티어이지만, 쉬운 문제를 빠르게 푸는 능력을 기르는 것 외에도 자신감을 높이기 위한 목적도 있어서 골드 문제를 포함하지 않았습니다.

 

그래서 오늘의 '시프트 마음대로' 결과는...!

1645번: 성지의 생일파티

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

1645번: 성지의 생일파티

테스트 케이스가 맞길래 제출했다가 3번을 틀리고 나서야 '초대되지 않은 학생의 생각은 고려할 필요 없다'는 것을 깨닫게 되었습니다.

그걸 알고 다시 구현하니 맞더라고요...

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

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

    sort(all(ks));
    int ans = ks[0];
    if (ans == 0) ans = 1;
    else while (ks[ans-1] > ans-1) ++ans;

    cout << ans;

    return 0;
}

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

현 시점 난이도: 실버 IV

10332번: Shopping

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

10332번: Shopping

대충 페어를 잘 정렬해둔 다음에 '강의실 배정' 문제 풀듯이 그리디하게 접근하면 되겠거니 하는 건 금방 알았습니다.

그런데 어찌된 영문인지 정렬을 제대로 했는데도 계속 틀리더라구요. 그래서 우선순위 큐를 쓰는 걸로 바꿔 구현했더니 바로 맞혔어요.

알고 보니까 사용한 자료구조의 문제가 아니라 사소한 실수여서 아쉬웠네요.

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

    int N, m;
    cin >> N >> m;
    priority_queue<pii> res;
    forn(i, 0, m-1) {
        int c, d;
        cin >> c >> d;
        res.push(MP(-c, -d));
    }

    int ans = 0;
    int cur = 0;
    while (!res.empty()) {
        int left = -res.top().F;
        int right = -res.top().S;
        res.pop();
        while (!res.empty() && right >= -res.top().F) {
            right = max(right, -res.top().S);
            left = min(left, -res.top().F);
            res.pop();
        }
        ans += (right - cur) + (right - left);
        cur = left;
    }
    ans += (N + 1) - cur;

    cout << ans;

    return 0;
}

알고리즘 분류: 그리디 알고리즘, 정렬, 스위핑

현 시점 난이도: 실버 I

6161번: iCow

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

6161번: iCow

그냥 문제 상황을 잘 구현하면 됩니다. 그런데, 이 문제도 계속 틀린 끝에서야 '배분 후 나머지 점수를 주는 기준'이 그냥 인덱스 순이라는 걸 알게 되었습니다...

사실 그걸 바로 알았더라도 아주 만만한 문제는 아니긴 합니다.

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

    int N, T;
    cin >> N >> T;
    vector<int> R(N);
    int mx = 0;
    int mxi = -1;
    forn(i, 0, N-1) {
        cin >> R[i];
        if (mx < R[i]) {
            mxi = i;
            mx = R[i];
        }
    }

    forn(_, 1, T) {
        cout << mxi + 1 << "\n";
        int dist = R[mxi] / (N - 1);
        int left = R[mxi] % (N - 1);
        R[mxi] = 0;
        mx = 0;
        int nmxi = -1;
        forn(i, 0, N-1) {
            if (i != mxi) {
                R[i] += dist;
                if (i < left) R[i] += 1;
                if (left >= mxi && i == left) R[i] += 1;
            }
            if (mx < R[i]) {
                nmxi = i;
                mx = R[i];
            }
        }
        mxi = nmxi;
    }

    return 0;
}

알고리즘 분류: 구현, 시뮬레이션

현 시점 난이도: 브론즈 I

9693번: 시파르

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

9693번: 시파르

Python으로 풀기로 한 문제인데, 계속 시간 초과가 발생해서 파이썬 문제인가 싶었지만..

겨우 통과를 한 다음에 다른 사람들의 코드를 쭉 훑어보니 제가 비효율적으로 짠 게 맞더라고요.

아래는 효율적인 코드를 공유합니다!

import sys
input = sys.stdin.readline

N = int(input())
x = 1
while N:
    # twos are always greater than fives
    fives = 0
    while N:
        fives += N // 5
        N //= 5
    print(f"Case #{x}: {fives}")
    x += 1
    N = int(input())

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

현 시점 난이도: 실버 IV

---

생각보다 랜덤 디펜스가 매우 힘들군요...

특히 수학 부분이 약한데, 문제 상황 알아듣는 것에서부터 불협화음이 발생해 버리니 쉽지 않았어요.

빨리 강해지고 싶습니다 ㅠㅠ