취미로 코딩하기

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

이번에 볼 문제는 백준 33526번 문제인 Anti-Fan Death이다.
문제는 아래 링크를 확인하자.

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

\(N\)이 2 이상일 때, 각 문자로 이루어진 \(N\times N\)블록 9개로 구성된 \(3N\times 3N\) 판을 적절히 구성하면 어떤 연속한 세 개의 문자도 같은 두 개의 문자를 포함하며 각 행과 열에 각 문자가 \(N\)개씩 포함되게 할 수 있다는 점을 관찰하자.

따라서 \(N\)이 1일 때의 답을 구하고, 나머지 답을 위와 같은 방법으로 구성해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;
char A[3][3] = {{'Z','N','A'},{'N','A','Z'},{'A','Z','N'}};

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

    cin >> N;
    for (int r = 0; r < 3; r++) {
        for (int p = 0; p < N; p++) {
            for (int c = 0; c < 3; c++) {
                for (int k = 0; k < N; k++) cout << A[r][c];
            }
            cout << '\n';
        }
    }
}

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

이번에 볼 문제는 백준 33515번 문제인 노트북 세 대를 가지고 왔다이다.
문제는 아래 링크를 확인하자.

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

주어지는 두 가지 시간 중 어떤 시간보다도 늦게 형진이가 문제를 해결하면 형진이의 노트북으로 대회를 참여할 수 없다. 그러나 형진이가 두 가지 시간 이하의 시간으로 문제를 해결하면 형진이의 노트북으로 대회를 참여할 수 있다.

따라서 주어지는 두 값 중 다른 값보다 작거나 같은 값이 문제의 답이 된다.

조건문 또는 min함수를 이용하여 문제를 해결하자.

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

#include <iostream>
using namespace std;

int x, y;

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

    cin >> x >> y;
    cout << min(x, y);
}

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

이번에 볼 문제는 백준 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';
    }
}