취미로 코딩하기

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

이번에 볼 문제는 백준 33540번 문제인 Helping Out 이다.
문제는 아래 링크를 확인하자.

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

각 플레이어마다 주어지는 점수의 합을 구하는 문제이다.

map 자료구조를 이용하면 문자열에 대응되는 정수를 간단히 저장 및 수정할 수 있다. 또한 (ordered) map은 자료를 오름차순으로 저장하므로 답안을 사전순으로 출력하기에도 매우 유용하다.

따라서 map을 이용하면 문제를 간단하게 해결할 수 있다.

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

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

int K;
map<string, int> mp;

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

    cin >> K;
    while (K--) {
        string s; int x; cin >> s >> x;
        mp[s] += x;
    }

    for (auto &p:mp) cout << p.first << ' ' << p.second << '\n';
}

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

이번에 볼 문제는 백준 33531번 문제인 Donor Time!이다.
문제는 아래 링크를 확인하자.

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

1부터 \(N\)까지의 번호가 매겨진 정점과 해당 정점들을 잇는 \(S\)개의 양방향 에지가 있을 때 가장 가까운 Donor shop이 어디인지, 그리고 그 거리가 몇인지를 구하는 문제이다. 단, 가장 가까운 Donor Shop이 여럿 존재한다면 번호가 가장 작은 Donor Shop을 찾아야 한다.

1번 정점으로부터 다른 모든 정점까지의 최단거리는 dijkstra 알고리즘을 이용하여 한번에 모두 구할 수 있다. 따라서 이 문제는 dijkstra 알고리즘을 활용하는 것으로 쉽게 해결할 수 있다.

이 문제의 경우 모든 에지의 길이가 1 이상이므로, dijkstra 과정에서 방문하는 노드의 순서를 1번 정점으로부터 가장 가까운 순으로, 거리가 같다면 번호가 작은 순으로 어렵지 않게 뽑을 수 있어 조건을 만족하는 정점을 찾자마자 해당 답을 출력 후 프로그램을 중간에 종료시켜도 괜찮다.

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

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

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

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

    cin >> N >> M;
    while (M--) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }
    cin >> M;
    while (M--) {
        int x; cin >> x;
        donor[x] = 1;
    }
    dijkstra();
}

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

이번에 볼 문제는 백준 33532번 문제인 Efficient Printing이다.
문제는 아래 링크를 확인하자.

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

어떤 양의 정수의 10진수 표기의 0의 개수는 이 정수가 10으로 몇 번 나누어떨어지는지를 말해준다. 10으로 나누어떨어지는 횟수는 이 정수가 2와 5를 소인수로 몇 개씩 가지고 있는지를 구해 둘 중 작은 값을 찾는 것으로 구할 수 있다.

한편, \(n!\)의 경우 소인수 2의 개수가 5의 개수보다 항상 많거나 같으므로, 문제에서 구하고자 하는 값은 소인수 5의 개수를 구하는 것으로 알 수 있다.

이는 5의 1승, 2승, 3승... 의 배수가 \(n\) 이하의 양의 정수 중 각각 몇개 있는지를 이용해 계산할 수 있다는 점이 잘 알려져있다.

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

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

ll N, K = 5, ans;

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

    cin >> N;
    while (K <= N) ans += N / K, K *= 5;
    cout << ans;
}

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

이번에 볼 문제는 백준 33488번 문제인 아름다운 수열이다.
문제는 아래 링크를 확인하자.

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

\(|i-j|\)가 소수이면 \(|a_i-a_j|\)도 소수임을 만족하는 수열 \(a_n\)을 하나 찾는 문제이다.

\(|i-j|\)와 \(|a_i-a_j|\) 두 식의 구조가 비슷하다는 점을 눈여겨보자. 이를 파고들면 \(a_k=k\)와 같은 수열의 경우 \(|a_i-a_j|=|i-j|\)이므로 위의 조건을 항상 만족함을 관찰할 수 있다.

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

#include <iostream>
using namespace std;

int T, N;

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

    cin >> T;
    while (T--) {
        cin >> N;
        cout << "YES\n";
        for (int i = 1; i <= N; i++) cout << i << ' ';
        cout << '\n';
    }
}

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

이번에 볼 문제는 백준 5714번 문제인 Isoceles Triangles이다.
문제는 아래 링크를 확인하자.

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

세 점이 모두 정수점인 정삼각형은 존재하지 않으므로, 각각의 이등변삼각형은 길이가 같은 두 변에 공통으로 포함될 꼭짓점을 먼저 정하고 그 점으로부터 거리가 같은 두 점을 고르는 식으로 모두 찾을 수 있다는 점을 관찰하자.

따라서, 각 점에 대하여 그 점을 제외한 모든 점까지의 거리를 모두 구한 뒤 그 중 같은 거리에 있는 점들끼리의 개수를 각각 이용해 문제를 해결할 수 있다.

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

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

ll N;
ll P[1000][2], A[1000];

void solve() {
    ll ans = 0;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ll dx = P[i][0] - P[j][0], dy = P[i][1] - P[j][1];
            A[j] = dx * dx + dy * dy;
        }
        sort(A, A + N);
        ll old = -1, combo = 0;
        for (int j = 0; j < N; j++) {
            if (A[j] == old) combo++;
            else old = A[j], ans += combo * (combo - 1) / 2, combo = 1;
        }
        ans += combo * (combo - 1) / 2;
    }
    cout << ans << '\n';
}

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

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

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

이번에 볼 문제는 백준 21430번 문제인 Свечки이다.
문제는 아래 링크를 확인하자.

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

어떤 직선과 그 직선 위에 놓여있지 않은 점에 대하여, 점이 직선의 어느 쪽에 있느냐에 따라 \(ax+by+c\)의 부호가 변한다는 점을 관찰하자. 또한 직선으로 나뉘어진 각 영역은 각 직선에 대하여 어느 쪽에 있는지를 모두 기록한 것으로 구분된다는 점을 관찰하자.

이를 이용하면, \(m\)개의 비트를 이용하여 각 직선마다 어느 쪽에 점이 있는지를 기록할 수 있게 된다. 이 중 중복되는 값이 있는지를 살펴 문제를 해결하자.

각 직선을 비트로 저장하는 대신 trie 자료구조를 활용해도 좋다.

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

#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;

int N, M, R;
int P[10000][2];
vector<bool> st[10000];

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

    cin >> N >> M >> R;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) st[i].resize(M);
    for (int j = 0; j < M; j++) {
        int A, B, C; cin >> A >> B >> C;
        for (int i = 0; i < N; i++) {
            if (A * P[i][0] + B * P[i][1] + C > 0) st[i][j] = 1;
        }
    }
    sort(st, st + N);
    for (int i = 0; i + 1 < N; i++) {
        if (st[i] == st[i + 1]) {
            cout << "YES";
            return 0;
        }
    }
    
    cout << "NO";
}