취미로 코딩하기

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 34803번 문제인 문자열 로또이다.
문제는 아래 링크를 확인하자.

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

주어진 제한조건에서, 각 문자열에서 얻을 수 있는 길이 \(K\)의 부분문자열은 총 \(L-K+1\)개임을 관찰하자.

따라서 주어진 문제는 총 \(N(L-K+1)\)개의 부분문자열 중 가장 많이 등장한 문자열의 등장 횟수를 구하는 문제로 볼 수 있다.

모든 부분문자열의 길이는 100 이하이고 부분문자열의 총 개수는 2000 이하이므로, 정렬이나 map 등을 이용하여 각 각 부분문자열의 등장 횟수를 구해 문제를 해결할 수 있다.

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

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

int L, N, K, ans;
string s[20];
map<string, int> mp;

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

    cin >> L >> N;
    for (int i = 0; i < N; i++) cin >> s[i];
    cin >> K;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k + K <= L; k++) mp[s[i].substr(k, K)]++;
    }

    for (auto &p:mp) ans = max(ans, p.second);
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

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

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

100만 미만의 양의 정수 \(m\)이 주어질 때, \(m\)의 자기 자신을 제외한 약수 중 일부(전체도 가능)의 합으로 \(m\)을 만들 수 있는지를 판별하는 문제이다.

100만 미만의 정수 중 가장 많은 수는 240개의 약수를 가진다(720720 등). 따라서 \(m\)의 모든 약수를 활용하여 \(m\)을 생성할 수 있는지 판단하는 방식으로 문제를 충분히 해결할 수 있다.

이러한 유형의 문제를 해결하는 대표적인 방법으로 knapsack dp가 있다. 특히 이 문제에서는 존재의 여부만을 확인하면 되므로 0과 1로 모든 상태를 표현할 수 있고, 따라서 비트셋을 활용한 knapsack 구현이 가능하다. 글쓴이는 이를 활용하여 문제를 해결하였다.

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

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

int T;
bitset<1000000> st;

bool func(int n) {
    st = 0;
    st[0] = 1;
    for (int i = 1; i * i <= n; i++) {
        if (n % i) continue;
        if (i != n) st = (st << i) | st;
        if (n / i != n && n / i != i) st = (st << (n / i)) | st;
    }
    return st[n];
}

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

    cin >> T;
    while (T--) {
        int x; cin >> x;
        if (func(x)) cout << "Semiperfect\n";
        else cout << "NOT Semiperfect\n";
    }
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

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

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

주어진 문제의 상황을 각 하수구를 노드로, 물이 흐를 수 있는 두 하수구의 관계를 방향이 있는 에지로 하는 그래프로 모델링해보자. 이와 같은 모델에서 주어진 문제는 그래프의 모든 노드에서 입력으로 주어진 "물이 고이지 않는 하수구" 노드 중 적어도 하나에 도달할 수 있는지를 판단하는 것으로 해결할 수 있게 된다.

그러나 각 노드마다 "물이 고이지 않는 하수구"에 도달할 수 있는지 한 번씩 탐색해보는 것은 비효율적이다. 특히, 잘 구성된 일자 그래프가 주어지면 시간초과가 발생하게 된다. 다른 방법을 생각해보자.

각 노드에서 어떤 "물이 고이지 않는 하수구"에 도달할 수 있다는 것은, 주어진 그래프와 간선의 방향을 뒤집은 그래프(Transpose Graph라고 부른다)에서 각 노드마다 도달할 수 있는 "물이 고이지 않는 하수구"가 적어도 하나씩 있다는 것과 같다는 점을 관찰하자. 따라서, 주어진 "물이 고이지 않는 하수구" 노드로부터 도달할 수 있는 노드의 집합이 전체 노드의 집합과 같은지를 판단하는 것으로 문제를 해결할 수 있다.

이와 같은 문제 상황은 multisource BFS 등으로 어렵지 않게 해결할 수 있다. 글쓴이는 그냥 스택을 이용하여 그래프 탐색을 진행하였다.

높이가 같은 두 하수구 사이에서는 배수로가 있어도 어떠한 방향 에지도 생성되지 않는다는 점에 주의하자.

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

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

int N, M, K;
int H[200001];
bool visited[200001];
vector<int> G[200001];
vector<int> stk;

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

    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> H[i];
    while (M--) {
        int x, y; cin >> x >> y;
        if (H[x] > H[y]) G[y].emplace_back(x);
        else if (H[x] < H[y]) G[x].emplace_back(y);
    }

    cin >> K;
    while (K--) {
        int x; cin >> x;
        visited[x] = 1;
        stk.emplace_back(x);
    }
    while (!stk.empty()) {
        int x = stk.back(); stk.pop_back();
        for (auto &nxt:G[x]) {
            if (visited[nxt]) continue;
            visited[nxt] = 1;
            stk.emplace_back(nxt);
        }
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) cout << "flood", exit(0);
    }
    cout << "no flood";
}

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

이번에 볼 문제는 백준 29338번 문제인 Склад Оби-Вана Кеноби이다.
문제는 아래 링크를 확인하자.

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

앞 절반의 원소를 들고 있는 덱과 뒤 절반의 원소를 들고 있는 덱을 관리하자.

자료를 이렇게 관리하면 주어지는 모든 쿼리를 \(O(1)\)에 어렵지 않게 처리할 수 있게 되므로 문제를 간단히 해결할 수 있다.

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

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

int Q;
deque<int> L, R;

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

    cin >> Q;
    while (Q--) {
        string s; cin >> s;
        if (s.front() == 'a') {
            int x; cin >> x;
            R.push_back(x);
        }
        else if (s.front() == 't') {
            if (!R.empty()) R.pop_back();
        }
        else swap(L, R);
        while (L.size() > R.size()) R.push_front(L.back()), L.pop_back();
        while (L.size() + 1 < R.size()) L.push_back(R.front()), R.pop_front();
    }

    cout << L.size() + R.size() << '\n';
    for (auto &x:L) cout << x << ' ';
    for (auto &x:R) cout << x << ' ';
}

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

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