취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 32941번 문제인 왜 맘대로 예약하냐고이다.
문제는 아래 링크를 확인하자.

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

각 조원에 대하여 참석 가능한 교시 중 \(X\)교시가 있는지 확인하자. 만약 \(X\)교시에 참석이 불가능한 조원이 한 명이라도 있으면 답은 "NO"가 되고, 그렇지 않다면 답은 "YES"가 된다.

위 내용의 구현은 반복문과 조건문을 적절히 활용하는 것으로 해낼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T, X, N, K;

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

    cin >> T >> X >> N;
    while (N--) {
        bool chk = 0;
        cin >> K;
        while (K--) {
            int x; cin >> x;
            if (x == X) chk = 1;
        }
        if (!chk) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 32953번 문제인 회상이다.
문제는 아래 링크를 확인하자.

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

한 과목당 같은 학번은 단 한 번씩 주어지므로, 등장하는 학번이 각각 몇 번씩 나오는 지 세는 것으로 문제를 충분히 해결할 수 있다.

등장하는 학번의 개수를 세는 것은 크기 2천만인 배열을 이용하거나 map을 이용하는 등 여러 방법으로 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
using namespace std;

int N, M, x, K, ans;
map<int, char> mp;

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

    cin >> N >> K;
    while (N--) {
        cin >> M;
        while (M--) {
            cin >> x; mp[x]++;
        }
    }
    for (auto &p:mp) {
        if (p.second >= K) ans++;
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11643번 문제인 The Magical 3이다.
문제는 아래 링크를 확인하자.

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

어떤 양의 정수 \(n\)의 \(b\)진법으로 나타냈을 때의 일의 자리가 3이라는 것은 \(3<b\)이며 \(n\)을 \(b\)로 나누었을 때의 나머지가 \(k\)와 같다는 것과 동치이다. 따라서 \(n-3\)은 음이 아닌 \(b\)의 배수여야 한다.

위의 관찰을 이용하면 답의 후보로 살펴야 하는 수는 \(n-3\)의 약수 뿐임을 알 수 있다. \(n-3\)의 모든 약수에 한 번씩 접근하여 가능한 답의 최솟값을 구해 문제를 해결하자. 이는 테스트케이스 당 시간복잡도 \(O(\sqrt{n})\)에 수행할 수 있다.

아래는 제출한 소스코드이다.

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

ll N;

void solve() {
    if (N < 3) {
        cout << "No such base\n";
        return;
    }
    else if (N == 3) {
        cout << 4 << '\n';
        return;
    }
    N -= 3;
    ll ans = 1000000000000000007LL;
    for (ll k = 1; k * k <= N; k++) {
        if (N % k) continue;
        if (k > 3) ans = min(ans, k);
        if (N / k > 3) ans = min(ans, N / k);
    }
    if (ans < 1000000000000000007LL) cout << ans << '\n';
    else cout << "No such base\n";
}

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

    cin >> N;
    while (N) {
        solve();
        cin >> N;
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1800번 문제인 인터넷 설치이다.
문제는 아래 링크를 확인하자.

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

문제를 다른 시각으로 해석해보자. 1번 컴퓨터와 \(N\)번 컴퓨터를 이을 수 있다는 전제 하에, 주어진 문제는 "어떤 \(x\)에 대하여 비용 \(x\)를 넘는 에지를 \(K\)개 이하로 사용해 1번 컴퓨터와 \(N\)번 컴퓨터 사이를 이을 수 있는 최소 \(x\)는 무엇인지"를 찾는 문제로 생각할 수 있다. 어떤 \(x\)값에 대하여 두 컴퓨터를 이을 수 있다면 그보다 큰 \(x\)값이 주어져도 두 컴퓨터를 이을 수 있으며 두 컴퓨터를 이을 수 없다면 그보다 작은 \(x\)값이 주어져도 두 컴퓨터를 이을 수 없으므로, \(x\)의 값은 이진탐색을 이용해 계산할 수 있다.

두 컴퓨터가 이어질 수 있는지를 생각해야 한다는 점을 잊지 말자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int N, E, K;
vector<pair<int, int>> G[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int dist[1001];
bool dijkstra(int mid) {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        int cur = pq.top().second, d = pq.top().first; pq.pop();
        if (dist[cur] < d) continue;
        for (auto &p:G[cur]) {
            int nxt = p.first, dd = d;
            if (p.second > mid) dd++;
            if (dd < dist[nxt]) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
        }
    }
    return (dist[N] <= K);
}

int L, R = 1000001;

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

    cin >> N >> E >> K;
    while (E--) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }

    while (L < R) {
        int mid = (L + R) / 2;
        if (dijkstra(mid)) R = mid;
        else L = mid + 1;
    }
    if (L == 1000001) cout << -1;
    else cout << L;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14476번 문제인 최대공약수 하나 빼기이다.
문제는 아래 링크를 확인하자.

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

최대공약수는 유클리드 호제법으로 빠르게 구할 수 있다.

어떤 한 수를 제외한 다른 모든 수의 최대공약수는 그 수의 왼쪽에 있는 모든 수의 최대공약수와 오른쪽에 있는 모든 수의 최대공약수와 같음을 관찰하자. 따라서 왼쪽부터의 \(i\)번째 수까지의 최대공약수를 계산해 둔 배열과 오른쪽부터 \(i\)번째 수까지의 최대공약수를 계산해 둔 배열을 각각 \(O(N\lg N)\)에 구해두면 \(i\)번째 수를 제외한 수의 최대공약수를 각각 \(\lg N\)에 계산할 수 있게 된다.

각 수에 대하여 그 수를 제외한 나머지 수의 최대공약수를 계산하고, 그 중 문제의 조건을 만족하는 최대공약수수의 최댓값과 그 때의 인덱스를 저장해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
    if (y) return gcd(y, x % y);
    return x;
}

int N, ans = -1, aidx;
int A[1000002], L[1000002], R[1000002];

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

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) L[i] = gcd(L[i - 1], A[i]);
    for (int i = N; i > 0; i--) R[i] = gcd(R[i + 1], A[i]);
    for (int i = 1; i <= N; i++) {
        int val = gcd(L[i - 1], R[i + 1]);
        if (A[i] % val) {
            if (ans < val) ans = val, aidx = i;
        }
    }
    if (ans < 0) cout << ans;
    else cout << ans << ' ' << A[aidx];
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1451번 문제인 직사각형으로 나누기이다.
문제는 아래 링크를 확인하자.

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

어떤 직사각형을 두 개의 직사각형으로 나누는 방법은 가로방향이나 세로방향으로 한 번 자르는 것 외에는 없다. 그리고 세 개의 직사각형으로 나누는 방법은 (1)가로 방향이나 세로 방향으로 두 번 자르거나 (2) 가로 방향으로 한 번 자르고 그 결과로 나온 직사각형 중 하나를 세로로 한 번 자르거나 (3) 세로 방향으로 한 번 자르고 그 결과로 나온 직사각형 중 하나를 가로로 한 번 자르는, 총 세 가지 외에는 없다.

위의 관찰을 이용하여 자를 수 있는 모든 방법에 대하여 직사각형의 합의 곱을 계산해 그 중 최댓값을 구하자. 2차원 누적 합 배열을 이용하면 위의 계산을 효율적으로 할 수 있을 것이다.

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

int R, C; ll ans;
ll A[51][51];

ll func(int r1, int c1, int r2, int c2) {
    return A[r2][c2] - A[r1 - 1][c2] - A[r2][c1 - 1] + A[r1 - 1][c1 - 1];
}

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

    cin >> R >> C;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            char x; cin >> x;
            A[r][c] += x - '0';
            A[r][c] += A[r - 1][c] + A[r][c - 1] - A[r - 1][c - 1];
        }
    }
    for (int r1 = 1; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            ans = max(ans, func(1, 1, r1, C) * func(r1 + 1, 1, r2, C) * func(r2 + 1, 1, R, C));
        }
    }
    for (int c1 = 1; c1 < C; c1++) {
        for (int c2 = c1 + 1; c2 < C; c2++) {
            ans = max(ans, func(1, 1, R, c1) * func(1, c1 + 1, R, c2) * func(1, c2 + 1, R, C));
        }
    }

    for (int r = 1; r < R; r++) {
        for (int c = 1; c < C; c++) {
            ans = max(ans, func(1, 1, r, c) * func(1, c + 1, r, C) * func(r + 1, 1, R, C));
            ans = max(ans, func(1, 1, r, C) * func(r + 1, 1, R, c) * func(r + 1, c + 1, R, C));
        }
    }
    for (int c = 1; c < C; c++) {
        for (int r = 1; r < R; r++) {
            ans = max(ans, func(1, 1, r, c) * func(r + 1, 1, R, c) * func(1, c + 1, R, C));
            ans = max(ans, func(1, 1, R, c) * func(1, c + 1, r, C) * func(r + 1, c + 1, R, C));
        }
    }
    cout << ans;
}

아래는 제출한 소스코드이다.