220719 백준 풀이 : BOJ 18977, BOJ 25369, BOJ 25370 등

오랜만에 코드포스(Codeforces) 라운드에 참가하려고 했는데 7시에 방 와서 혼밥하고 너무 피곤해서 그대로 뻗어버렸다.

일어나보니 시간은 12시 반이 넘어있었다.

코드포스 라운드 많이 치겠다고 다짐했는데 정작 최근에 아예 안 풀어서 진짜로 지금 배치 보면 그린 나올 것 같다.

아무튼 오늘도 백준 문제 풀이를 해보자.

 

 

백준 BOJ 18977번 : Maximum Multiple

문제 난이도 : Silver I

알고리즘 분류 : 정수론

 

(새벽에 백준을 들어갔는데 진짜 우연히 koosaga님의 제출이 맨 위에 있길래 무슨 문제일까 궁금해서 풀어봤다.)

 

주어진 N에 대해, x + y + z = N이고 x | N, y | N, z | N인 순서쌍 (x, y, z) 중 xyz 값의 최대를 구하는 문제이다.

 

ax = N, by = N, cz = N으로 두고 첫 번째 식을 x로 나누면 1 + (y + z)/x = a이므로 x | (y + z)임을 알 수 있다.

마찬가지로 y, z도 나머지 두 수의 합의 약수가 된다.

이것은 굉장히 강력한 조건으로써 가능한 경우가 x = k, y = k, z = k 또는 x = k, y = k, z = 2k (순서 무관) 뿐이다.

따라서 N = 3k 또는 N = 4k인 경우에 대해 위의 두 값의 곱을 구해주면 된다.

단, N이 12의 배수일 수도 있는데 이 경우는 3k로 나누는 경우가 xyz 값이 더 크므로 if문을 작성할 때 N % 3 == 0인 경우부터 처리하자.

 

 

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

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

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        if(N % 3 == 0) cout << (N/3)*(N/3)*(N/3) << "\n";
        else if(N % 4 == 0) cout << (N/2)*(N/4)*(N/4) << "\n";
        else cout << -1 << "\n";
    }
}

 

 

백준 BOJ 18867번 : 편지 꼭 해다오

문제 난이도 : Silver II

알고리즘 분류 : 런타임 전의 전처리

 

제출되는 입력을 1byte 단위로 끊어서 int형으로 캐스팅 한 문자를 x_i라고 했을 때, x_i^814들의 합의 mod 20200429가 20200402가 되면 정답 처리를 받는 문제이다.

즉, 위의 조건을 만족하는 text를 답으로 제출하는 문제이다.

 

우리는 이 조건을 만족하는 문자열의 최소 길이가 몇인지 모르지만 짧을수록 구하기 용이할 것이다.

길이를 몰라도 조건을 만족하는 문자열을 구하는 코드를 작성할 수 있지만, 최대한 간략하게 답을 구하고자, 정답 처리를 받은 다른 제출의 길이를 확인해보자.

 

 

 

보면 5 byte의 제출로 정답을 받은 사람들이 많다.

그렇다면 5자리 문자열 정답이 존재한다는 뜻이 된다.

따라서 다음과 같이 재귀함수를 이용하여 조건을 만족하는 길이가 5인 수열을 찾아보자.

 

 

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

int mod = 20200429;
vector<int> v(101), u(101, 1), w;

void f(int cnt, int sum) {
    if(cnt >= 5) {
        if(sum % mod == 20200402) {
            for(int i=0; i<w.size(); i++) cout << w[i] << " ";
            cout << "\n";
            exit(0);
        }
        return;
    }

    for(int i=33; i<=100; i++) {
        w.push_back(v[i]);
        f(cnt + 1, sum + u[i]);
        w.pop_back();
    }
}

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

    for(int i=1; i<=100; i++) v[i] = i;

    for(int i=1; i<=100; i++) {
        for(int j=0; j<814; j++)
            u[i] = (u[i] * v[i]) % mod;
    }

    f(0, 0);
}

 

아스키코드 중 우리가 문자로써 입력할만한 값은 33부터이므로, 적당히 33 ~ 100 사이에서 해를 찾을 수 있도록 하였다.

위의 코드를 돌려본 결과는 다음과 같다.

 

 

 

이제 위의 아스키코드에 해당하는 문자를 순서대로 입력하여 답을 찾으면 된다.

참고로 96번 기호가 무엇인지 분간이 가지 않을 수 있는데, 다음의 자료를 참고하자.

 

 

 

` ← 이 부호이다.

따라서 정답 처리를 받는 제출 소스는 다음과 같다. (text로 제출해야 한다.)

 

!/5`d

 

 

백준 BOJ 25369번 : 카드 숫자 곱을 최소로 만들기

문제 난이도 : Silver II

알고리즘 분류 : 브루트포스

 

N장의 카드가 주어질 때, 1~9 중 중복 제한 없이 뽑아서 만들 수 있는 카드 중 N장의 카드 곱보다 곱이 큰 조합을 구하는 문제이다. (이 때 사전순으로 가장 앞서는 답을 출력해야 한다.)

 

생각해보면 N자리 카드의 조합이라는 것은 10^(N-1) ~ 10^N의 자연수 중 0이 없는 자연수의 모음으로 생각할 수 있다.

이 문제는 N이 7 이하이므로 특정 N에 대해 시간 내에 해결이 충분히 가능하다.

따라서 N자리 정수에 대해 곱이 주어진 카드 조합의 곱보다 큰 조합 중 가장 작은 조합을 구해주면 된다.

 

 

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

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

    int N; cin >> N;

    string num = "";
    int mul = 1;

    for(int i=0; i<N; i++) {
        char c; cin >> c;
        num += c;

        mul *= c - '0';
    }

    for(int i=pow(10, N-1); i<pow(10, N); i++) {
        string str = to_string(i);

        bool check = true;
        for(int j=0; j<str.length(); j++)
            if(str[j] == '0') check = false;
        if(!check) continue;

        int temp = 1;
        for(int j=0; j<str.length(); j++) temp *= str[j] - '0';

        if(temp > mul) {
            for(int j=0; j<str.length(); j++) cout << str[j] << " ";
            cout << "\n";
            return 0;
        }
    }

    cout << -1 << "\n";
}

 

 

백준 BOJ 25370번 : 카드 숫자 곱의 경우의 수

문제 난이도 : Silver II

알고리즘 분류 : 브루트포스

 

1~9 카드 중에 N장을 중복을 고려하지 않고 뽑아서 나오는 조합의 곱으로 나올 수 있는 경우의 수를 구하는 문제이다.

 

N이 7 이하이므로 모든 경우의 수를 따져보아도 시간이 충분하다.

따라서 재귀 함수를 활용하여 나올 수 있는 N개 카드의 곱의 조합을 모두 구하고, 중복을 제거한 뒤 벡터의 크기를 답으로 얻어주었다.

 

 

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

int N;
vector<int> v;

void f(int cnt, int mul) {
    if(cnt == N) {
        v.push_back(mul);
        return;
    }

    for(int i=1; i<=9; i++) {
        f(cnt+1, mul*i);
    }
}

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

    cin >> N;

    f(0, 1);

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

    cout << v.size() << "\n";
}

 

 

백준 BOJ 3079번 : 입국심사

문제 난이도 : Gold V

알고리즘 분류 : 이분 탐색

 

N개의 입국 심사대에 각각 걸리는 시간이 다르다고 할 때 M명이 입국 심사를 통과하는 최소 시간을 구하는 문제이다.

 

N이 10만 이하이므로 당연히 모든 케이스를 일일이 해볼 수는 없고 빠르게 구할 수 있는 방법을 사용해야 한다.

이분 탐색을 활용하여 시간을 미리 가정하고, M명 이상이 입국 심사를 통과할 수 있는지 확인한다.

만약 M명 이상이 입국 심사를 통과할 수 있으면 답을 갱신한 뒤 시간을 줄여준다.

반대로 M명 미만밖에 입국 심사를 통과할 수 없으면 시간을 늘려주면 된다.

 

다만 이 문제에서 의아한 점은 N = 1, a_i = 10^9, M = 10^9일 때 최대 소요 시간인 10^18이 되는데 l = 0, r= 10^18로 잡고 이분 탐색을 하면 오답 처리를 받는다.

그래서 현재 질문 게시판에 질문을 올려둔 상태이다.

해결이 된다면 수정하도록 하겠다.

 

참고로 정답 처리를 받으려면 아래와 같이 l = 0, r = ans = M * v_max로 잡아야 한다.

 

 

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

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

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

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

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

    int l = 0, r = M * v[N-1], ans = M * v[N-1];

    while(l <= r) {
        int m = (l + r)/2;

        int sum = 0;
        for(int i=0; i<N; i++) sum += m / v[i];

        if(sum >= M) {
            ans = min(ans, m);
            r = m - 1;
        }
        else l = m + 1;
    }

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

 

 

백준 BOJ 24023번 : 아기 홍윤

문제 난이도 : Gold V

알고리즘 분류 : 비트마스킹

 

길이 N인 수열에서 연속 부분 수열을 골라 그 or 연산 값이 M이 되는 수열의 양 끝 위치를 구하는 문제이다.

 

N이 10만 이하이고 "연속" 부분 수열을 찾는 O(N)에 풀이하는 것이 바람직하다.

부분 수열의 or 값이 M이 되기 위한 조건은 무엇일까?

생각해볼 수 있는 강력한 조건으로는, M의 비트가 0인 자리에는 다른 어떤 수도 비트 값으로 1을 가지지 않는다는 것이다.

즉, 부분 수열 a_i | M = M이 되어야 한다.

 

따라서 a_i | M != M인 a_i가 나타난다면 해당 수는 부분 수열이 될 수 없다.

그러므로 1번 위치를 left로 잡고, i를 이용하여 right 위치를 옮겨가면서 만약 a_i | M != M이면 left = i+1로 갱신해준 뒤 다시 탐색을 시작한다.

탐색 중에 left ~ right의 a_i 누적 or 값이 M이 된다면 그것을 답으로 출력하면 된다.

만약 탐색이 끝났음에도 조건을 만족하는 부분 수열을 찾지 못했다면 -1을 출력해주면 된다.

 

 

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

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

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

    vector<int> v(N+1);
    for(int i=1; i<=N; i++) cin >> v[i];

    int val = 0, l = 1;

    for(int i=1; i<=N; i++) {
        if((M | v[i]) == M) {
            val |= v[i];

            if(val == M) {
                cout << l << " " << i << "\n";
                return 0;
            }
        }
        else {
            l = i+1;
            val = 0;
        }
    }

    cout << -1 << "\n";
}

 

 

백준 BOJ 17087번 : 숨바꼭질 6

문제 난이도 : Silver II

알고리즘 분류 : 유클리드 호제법

 

X의 위치에서 X+D나 X-D로 여러 번 이동할 수 있다고 할 때, 모든 A_i에 도달하기 위한 D의 최댓값을 구하는 문제이다.

 

간단히 생각해보면 모든 abs(X - A_i)가 D의 배수이면 된다.

따라서 abs(X - A_i)들의 최대공약수가 답이 된다.

여러 수의 최대공약수는 gcd(gcd(a1, a2), a3) 이런 식으로 구할 수 있으므로 하나씩 쌍을 지어 gcd를 구하면 된다. 

 

 

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

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

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

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

    int ans = abs(M - v[0]);

    for(int i=1; i<N; i++)
        ans = __gcd(ans, abs(M - v[i]));

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

 

 

백준 BOJ 20126번 : 교수님의 기말고사

문제 난이도 : Silver III

알고리즘 분류 : 정렬

 

다른 시험들의 시작 시간과 시험 시간 길이가 주어질 때, 0 ~ K 시간 내에 길이 M의 시험을 시작할 수 있는 시간을 구하는 문제이다.

 

백준 BOJ 1931번 : '회의실 배정' 문제와 비슷한 느낌의 문제이다.

끝나는 시간을 기준으로 오름차순 정렬을 해주면, 다음 시험의 시작 시간과의 차이를 비교하여 길이 M인 시간을 볼 수 있는지 체크할 수 있다.

만약 하나라도 그러한 시간이 존재한다면 현재 시험이 끝나는 시간(= 시험을 시작할 수 있는 시간)을 출력 후 종료해주면 되고, 모든 반복문을 돌고도 시간이 존재하지 않는다면 -1을 출력해주면 된다.

 

이 문제의 핵심은 모든 시험의 맨 앞과 뒤에도 남는 시간을 체크해주어야 한다는 것이다.

그렇지 않으면 반례가 존재하여 WA를 받는다.

 

 

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

bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}

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

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

    vector<pair<int, int>> v(N+2);
    for(int i=1; i<=N; i++) {
        int a, b; cin >> a >> b;
        v[i] = {a, a + b};
    }
    v[N+1] = {K, K};

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

    for(int i=1; i<=N+1; i++) {
        if(v[i].first - v[i-1].second >= M && v[i-1].second + M <= K) {
            cout << v[i-1].second << "\n";
            return 0;
        }
    }

    cout << -1 << "\n";
}

 

 

백준 BOJ 8979번 : 올림픽

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

N개 국가의 금, 은, 동메달의 개수가 주어질 때 M번 국가의 등수를 구하는 문제이다.

 

동점자는 같은 등수일 때, 이를 처리하기 위한 가장 좋은 방법은 (자신보다 성적이 앞서는 사람의 수) + 1으로 등수를 계산하는 것이다.

따라서 국가 번호가 M에 해당하는 idx를 저장해주고, idx 국가보다 성적이 더 높은 국가의 수를 cnt 해주어 그 값에 1을 더한 것을 등수로 출력해주면 정답 처리를 받을 수 있다.

참고로 이 문제를 푸는 데 별도의 정렬은 필요하지 않다.

 

 

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

struct s { int n, a, b, c; };

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

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

    vector<s> v(N);
    int idx;

    for(int i=0; i<N; i++) {
        cin >> v[i].n >> v[i].a >> v[i].b >> v[i].c;

        if(v[i].n == M) idx = i;
    }

    int ans = 1;
    for(int i=0; i<N; i++) {
        if(v[i].a > v[idx].a) ans++;
        else if(v[i].a == v[idx].a && v[i].b > v[idx].b) ans++;
        else if(v[i].a == v[idx].a && v[i].b == v[idx].b && v[i].c > v[idx].c) ans++;
    }

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

 

 

백준 BOJ 5157번 : Bailout Bonus

문제 난이도 : Bronze III

알고리즘 분류 : 구현

 

기업의 번호와 금액이 주어질 때, 긴급 구제금을 받은 기업에 해당하면 특정 비율의 금액을 지불해야 한다고 가정하면 총 얼마에 금액이 지불되는지를 구하는 문제이다.

 

금액을 지불해야 하는 기업의 리스트를 벡터에 저장하고, 매 기업이 나올 때마다 지불해야 하는 기업에 해당하는지 일일이 확인해가면서 답을 구하면 된다.

문제가 길고 변수가 많아서 문제 해석이 어려울 수 있는데, 질문 탭에 보면 ez_code님이 문제 해석을 올려두셨으니 이를 참고하여 문제를 풀이하면 수월할 것이다.

 

 

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

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

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int C, B, N, r; cin >> C >> B >> N >> r;

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

        int ans = 0;
        for(int i=0; i<N; i++) {
            int a, b; cin >> a >> b;

            bool check = false;
            for(int j=0; j<B; j++)
                if(a == v[j]) check = true;

            if(check) ans += b * r / 100;
        }

        cout << "Data Set " << t << ":\n";
        cout << ans << "\n";
        cout << "\n";
    }
}

 

 

백준 BOJ 4850번 : Baskets of Gold Coins

문제 난이도 : Bronze III

알고리즘 분류 : 수학

 

주어지는 정수 N, w, d, sum에 대해 N개의 basket에서 1번 바구니에서는 질량이 w인 동전을 1개, 2번 바구니에서는 2개, ... 이런 식으로 N-1번 바구니에서는 N-1개, 그리고 N번 바구니에서만 동전을 0개 꺼낸다고 하며 하나의 바구니의 동전만 w-d의 질량을 가진다고 할 때 다른 질량을 가진 동전이 몇 번 바구니에 있는지 구하는 문제이다.

 

이는 유명한 수학 문제로, 원래 동전의 무게는 w * N * (N-1) / 2가 되어야하므로 sum 값과 차이를 구하여 d의 몇 배인지를 구하면 된다.

만약 diff/d가 0보다 크다면 diff/d번째 바구니가 정답이 되며, 그렇지 않을 경우 N번 바구니가 정답이 된다.

 

 

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

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

    int N, w, d, tot;

    while(cin >> N >> w >> d >> tot) {
        int sum = w * N * (N - 1) / 2;

        if(sum - tot > 0) cout << (sum - tot) / d << "\n";
        else cout << N << "\n";
    }
}