취미로 코딩하기

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

이번에 볼 문제는 백준 29703번 문제인 펭귄의 하루이다.
문제는 아래 링크를 확인하자.

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

주어진 문제 상황은 (좌표와 지금까지 물고기서식지를 방문한 적이 있는지 여부)를 정점으로, 이동 가능한 관계를 에지로 하는 그래프에서의 최단거리를 구하는 문제로 생각할 수 있다.

위 가중치가 없는 그래프에서의 최단거리를 BFS 등의 방법으로 구해 문제를 해결하자.

다른 풀이로, 출발지점과 도착지점에서 각각 다른 물고기서식지까지의 최단거리를 BFS를 통해 구한 다음 양쪽 모두에서 접근할 수 있는 물고기서식지의 두 거리의 합의 최솟값을 구하는 방법이 있다. 이동 방향이 반대여도 이동 거리는 그대로이므로 이러한 풀이가 성립한다는 점을 관찰하자.

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

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

int R, C, sR, sC, eR, eC;
char board[1000][1000];
int dist[1000][1000][2];
queue<pair<int, int>> que;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
void bfs() {
    dist[sR][sC][0] = 1;
    que.push(make_pair(sR, sC));
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second, sgn; que.pop();
        if (r < 0) r += R, sgn = 1;
        else sgn = 0;
        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == 'D' || dist[rr][cc][sgn]) continue;
            dist[rr][cc][sgn] = dist[r][c][sgn] + 1;
            if (sgn) rr -= R;
            que.push(make_pair(rr, cc));
        }
        if (!sgn && board[r][c] == 'F') dist[r][c][1] = dist[r][c][0] + 1, que.push(make_pair(r - R, c));
    }
}

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

    cin >> R >> C;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> board[r][c];
            if (board[r][c] == 'S') sR = r, sC = c, board[r][c] = 'E';
            else if (board[r][c] == 'H') eR = r, eC = c, board[r][c] = 'E';
        }
    }

    bfs();
    if (dist[eR][eC][1]) cout << dist[eR][eC][1] - 2;
    else cout << -1;
}

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

이번에 볼 문제는 백준 33656번 문제인 Island Exploration이다.
문제는 아래 링크를 확인하자.

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

전형적인 2차원 격자에서의 connected component의 크기를 구하는 문제이다.

이 유형의 문제는 flood-fill 계열의 탐색으로 문제를 해결할 수 있다.

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

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

int R, C, sR, sC, ans = 1;
char board[100][100];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
queue<pair<int, int>> que;

void bfs() {
    que.push(make_pair(sR, sC));
    board[sR][sC] = '.';
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second; que.pop();
        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (board[rr][cc] != '#') continue;
            board[rr][cc] = '.', ans++;
            que.push(make_pair(rr, cc));
        }
    }
}

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

    cin >> R >> C;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> board[r][c];
            if (board[r][c] == 'S') sR = r, sC = c;
        }
    }

    bfs();
    cout << ans;
}

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

이번에 볼 문제는 백준 33638번 문제인 Birthday Candles이다.
문제는 아래 링크를 확인하자.

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

끌 수 있는 촛불의 개수의 형태는 일부는 몇몇 사람의 초는 $k$개를 끄고 나머지 사람의 초는 $k+1$개를 끄는 형태뿐임을 관찰하자. (단, 0명도 가능하다.)

따라서, N명이 꽂은 초를 각각 그 사람이 꽂은 초 중 가장 비용이 적은 것을 골라 하나씩 끄는 것을 반복하는 것으로 문제를 쉽게 해결할 수 있다.

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

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

int N, H, C, ans;
priority_queue<int, vector<int>, greater<>> pq[100], pqpq;

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

    cin >> N >> H >> C;
    for (int n = 0; n < N; n++) {
        for (int h = 0; h < H; h++) {
            int x; cin >> x;
            pq[n].push(x);
        }
    }
    for (int h = 0; h < H; h++) {
        for (int n = 0; n < N; n++) pqpq.push(pq[n].top()), pq[n].pop();
        while (!pqpq.empty() && pqpq.top() <= C) {
            C -= pqpq.top();
            pqpq.pop();
            ans++;
        }
        if (!pqpq.empty()) break;
    }

    cout << ans;
}

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

이번에 볼 문제는 백준 33643번 문제인 Pencil Crayons이다.
문제는 아래 링크를 확인하자.

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

각 박스에 들어있는 크레용의 색이 겹치지 않도록 최소한의 크레용을 빼내자. 이 빼낸 크레용을 이용하여 다시 모든 박스를 서로 다른 색으로 채울 수 있음은 자명하다.

위 과정은 set 등의 자료구조를 이용하여 어렵지 않게 구현할 수 있다.

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

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

int N, K, ans;
set<string> st;

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

    cin >> N >> K;
    for (int n = 0; n < N; n++) {
        st.clear();
        for (int k = 0; k < K; k++) {
            string s; cin >> s;
            if (st.count(s)) ans++;
            else st.insert(s);
        }
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 33643번 문제인 Keys, Phone, Wallet이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열 중 "keys", "phone", "wallet"이 존재하는지를 판단하자. 그리고 등장한 적이 없는 물건을 모두 출력하자. 단, 모든 문자열이 등장한 경우 "ready"를 출력하자.

이는 간단한 반복문과 조건문을 이용하여 구현할 수 있다.

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

#include <iostream>
using namespace std;

int N, cnt;
bool iskeys, isphone, iswallet;

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

    cin >> N;
    while (N--) {
        string s; cin >> s;
        if (s == "keys") iskeys = 1;
        else if (s == "phone") isphone = 1;
        else if (s == "wallet") iswallet = 1;
    }
    if (!iskeys) cout << "keys\n";
    if (!isphone) cout << "phone\n";
    if (!iswallet) cout << "wallet\n";
    if (iskeys && isphone && iswallet) cout << "ready\n";
}

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

이번에 볼 문제는 백준 2450번 문제인 모양 정돈이다.
문제는 아래 링크를 확인하자.

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

주어진 모양의 정렬 결과는 각 도형이 등장하는 순서의 경우의 수와 같은 6가지뿐임을 관찰하자.

따라서 결과로 나올 수 있는 6가지 배치 각각에 대하여 필요한 최소 맞바꾸기 횟수를 구하는 것으로 문제를 해결할 수 있다.

각 경우에 대한 최소 맞바꾸기 횟수는 permutation cycle decomposition 개념을 활용하면 어렵지 않게 구할 수 있다.

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

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

int P[3] = {0,1,2};
bool comp(int &x, int &y) {
    return P[x] < P[y];
}

int N, ans = 0x3f3f3f3f;
int A[100000], B[100000];
int cnt[3][3];

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i], A[i]--;
    for (int i = 0; i < N; i++) B[i] = A[i];
    for (int k = 0; k < 6; k++) {
        sort(A, A + N, comp);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < N; i++) {
            cnt[A[i]][B[i]]++;
        }
        int val1 = min(cnt[0][1], cnt[1][0]);
        cnt[0][1] -= val1, cnt[1][0] -= val1;
        int val2 = min(cnt[0][2], cnt[2][0]);
        cnt[0][2] -= val2, cnt[2][0] -= val2;
        int val3 = min(cnt[1][2], cnt[2][1]);
        cnt[1][2] -= val3, cnt[2][1] -= val3;
        ans = min(ans, val1 + val2 + val3 + (cnt[1][0] + cnt[0][1]) * 2);
        next_permutation(P, P + 3);
    }

    cout << ans;
}