취미로 코딩하기

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

이번에 볼 문제는 백준 29343번 문제인 Шифровка이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열에 대하여, 1 이상 전체 길이 이하의 같은 길이의 접두사와 접미사 쌍 중 1개 이상의 모음을 포함하면서 같은 개수의 모음을 포함하는 쌍의 개수를 구하는 문제이다.

이는 각 접두사마다 모음이 몇 개 있는지, 접미사마다 모음이 몇 개 있는지를 이용해 어렵지 않게 계산할 수 있다.

길이가 \(k>1\)인 접두사에 포함된 모음의 개수는 길이가 \(k-1\)인 접두사에 포함된 모음의 개수와 \(k\)번째 문자의 모음 여부로 구할 수 있다는 점을 활용하자.

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

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

int N, val1, val2, ans;
string s;
int isvowel[128];

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

    isvowel['a'] = isvowel['e'] = isvowel['i'] = isvowel['o'] = isvowel['u'] = 1;
    isvowel['A'] = isvowel['E'] = isvowel['I'] = isvowel['O'] = isvowel['U'] = 1;
    cin >> N >> s;
    for (int L = 0, R = N - 1; L < N; L++, R--) {
        val1 += isvowel[s[L]], val2 += isvowel[s[R]];
        if (val1 && val1 == val2) ans++;
    }
    cout << ans;
}

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

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

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

입력으로 주어지는 문자열 중 문자 'C'로 시작하는 것의 개수를 세어 출력하는 문제이다.

string으로 입력을 받고 그 첫번째 문자를 확인하는 것으로 위의 작업을 간단하게 구현할 수 있다.

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

#include <iostream>
using namespace std;

int T, ans;
string s;

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

    cin >> T;
    while (T--) {
        cin >> s;
        if (s.front() == 'C') ans++;
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 33690번 문제인 포린드롬이다.
문제는 아래 링크를 확인하자.

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

먼저 한 자리 수(0 포함)는 주어진 조건을 항상 만족함을 관찰하자.

주어지는 조건을 만족하는 한 자리 이상의 수는 "두 자리 이상이면서 마지막 자리를 지운 수와 원래 수가 모두 팰린드롬인 수"로 해석할 수 있다. 한편, 두 수에서 서로 대응되는 위치에 있는 각 숫자의 쌍을 연결하면 이 조건을 만족하는 수를 구성하는 숫자가 모두 동일해야 함을 알 수 있다.

이러한 수는 몇 없으므로, \(N\) 이하의 수 중 이러한 수를 모두 생성하는 것으로 주어진 수 이하인지 확인하는 것으로 문제를 해결할 수 있다. 이는 111...1 꼴의 수에 1 이상 9 이하의 정수를 곱하는 것으로 모두 얻을 수 있다.

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

#include <iostream>
using namespace std;

int N, ans = 1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for (int i = 1; i < 1000000000; i = i * 10 + 1) {
        for (int k = 1; k < 10; k++) {
            if (i * k <= N) ans++;
        }
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 21275번 문제인 폰 호석만이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/probelm/21275

주어진 두 수를 2진수부터 36진수까지 각각의 진법으로 해석한 값을 먼저 계산해두자. 그리고 각각의 진법 쌍에 대하여 두 값이 같은지를 확인해 문제를 해결하자.

조건에 따라 두 진법이 서로 같으면 안 되며 각각의 값이 \(2^{63}\) 미만이어야 한다는 점에 유의하자.

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

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

lll MX = 9223372036854775807LL;
lll A[37], B[37];
string s;
ll aval, aidx, bidx, cnt;

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

    cin >> s;
    for (int b = 2; b < 37; b++) {
        for (auto &l:s) {
            int x;
            if ('0' <= l && l <= '9') x = l - '0';
            else x = 10 + l - 'a';
            if (x >= b) {
                A[b] = -1;
                break;
            }
            A[b] = A[b] * b + x;
            if (A[b] > MX) {
                A[b] = -1;
                break;
            }
        }
    }
    cin >> s;
    for (int b = 2; b < 37; b++) {
        for (auto &l:s) {
            int x;
            if ('0' <= l && l <= '9') x = l - '0';
            else x = 10 + l - 'a';
            if (x >= b) {
                B[b] = -1;
                break;
            }
            B[b] = B[b] * b + x;
            if (B[b] > MX) {
                B[b] = -1;
                break;
            }
        }
    }

    for (int i = 2; i < 37; i++) {
        for (int j = 2; j < 37; j++) {
            if (i != j && A[i] == B[j] && A[i] >= 0) aval = A[i], aidx = i, bidx = j, cnt++;
        }
    }

    if (cnt > 1) cout << "Multiple";
    else if (cnt == 1) cout << aval << ' ' << aidx << ' ' << bidx;
    else cout << "Impossible";
}

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

이번에 볼 문제는 백준 33574번 문제인 끊임없는 정렬과 창조함으로이다.
문제는 아래 링크를 확인하자.

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

주어지는 쿼리의 수가 3000 이하이므로 각 쿼리가 주어질 때의 배열의 크기 \(N\)은 3000 이하이다. 또한 크기가 \(N\)인 배열을 정렬하는 것은 \(O(N\lg N)\)의 시간복잡도로, 원소를 삽입하는 것은 \(O(N)\)의 시간복잡도로 수행할 수 있으므로 주어진 쿼리를 곧이곧대로 수행하는 시간복잡도는 \(O(N^2\lg N)\)이 되며, 이는 문제를 해결하기에 충분한 시간복잡도이다.

더 좋은 복잡도로 문제를 해결할 수도 있다. 정렬을 한번 수행하면 앞서 원소를 어디에 삽입했는지나 정렬을 했었는지 여부에 관계없이 항상 일정한 결과를 얻을 수 있다는 점을 이용하면 정렬을 단 한번만 수행해도 됨을 관찰하자. 또한, 이후 원소삽입과정은 세그먼트 트리 등의 자료구조를 이용하여 각 원소의 삽입될 위치를 관리하는 것으로 한번에 갱신해줄 수 있다.

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

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

int Q, N;
int A[3000];

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

    cin >> Q;
    while (Q--) {
        int q; cin >> q;
        if (q == 1) {
            cin >> q;
            if (q == 1) sort(A, A + N);
            else sort(A, A + N, greater<>());
        }
        else {
            int x, t; cin >> x >> t;
            for (int i = N - 1; i >= x; i--) A[i + 1] = A[i];
            A[x] = t;
            N++;
        }
    }
    cout << N << '\n';
    for (int i = 0; i < N; i++) cout << A[i] << ' ';
}

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

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