취미로 코딩하기

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

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

www.acmicpc.net/problem/1120

이 문제는 짧은 문자열의 앞과 뒤에 문자를 추가하여 긴 문자열과 길이를 같게 할 때, 두 문자열이 얼마나 덜 차이나게 할 수 있는지를 묻고 있다.

한편, 간단히 생각해보면, 짧은 문자열의 위치를 "긴 문자열과 가장 많이 일치하는 곳"에 놓고, 앞뒤로 긴 문자열과 동일하게 문자를 추가하는 것이 두 문자열이 가장 덜 차이나게 하는 방법이라는 것을 알 수 있다.

따라서, 문제에서 주어진 문자열의 길이가 작으므로, 반복문을 돌면서 두 문자열을 가장 많이 일치시킬 수 있는 위치를 찾으면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다. 코드를 읽는다면, 문제에는 짧은 문자열을 X, 긴 문자열을 Y라고 부르고 있으나 코드에서는 X와 Y를 각각 A와 B로 작성했다는 점을 유의하여 읽자.

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

int main()
{
    string A, B; cin >> A >> B;
    int Alen = (int)A.length(), Blen = (int)B.length();
    int maxmatching = 0;
    for (int i = 0;i <= Blen - Alen; i++) {
        int cnt = 0;
        for (int j = 0;j < Alen;j++) {
            if (A[j] == B[i + j]) cnt++;
        }

        maxmatching = max(maxmatching, cnt);
    }

    cout << Alen - maxmatching;
}

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

이번에 볼 문제는 백준 2476번 문제인 주사위 게임이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2476

이 문제에서는 문제에 주어진 대로, 나온 주사위 눈에 따라 조건문을 잘 작성해주면 된다.

다음과 같이 경우를 나누어 계산할 수 있다.

1) 세 주사위의 눈이 모두 같은 경우

2) 세 주사위의 눈이 모두 다른 경우

3) 두 개의 주사위의 눈이 같고 나머지 하나와 다른 경우:

3-1) 첫번째 주사위와 두번째 주사위의 눈이 같은 경우

3-2) 두번째 주사위와 세번째 주사위의 눈이 같은 경우

3-3) 세번째 주사위와 첫번째 주사위의 눈이 같은 경우

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

#include <iostream>
using namespace std;

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

    int ans = 0;
    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        int current;
        int x, y, z; cin >> x >> y >> z;
        if (x != y && y != z && z != x) current = max(max(x, y), z) * 100;
        else if (x == y && y == z) current = 10000 + x * 1000;
        else if (x == y) current = 1000 + x * 100;
        else if (y == z) current = 1000 + y * 100;
        else current = 1000 + z * 100; // (z == x)
        if (current > ans) ans = current;
    }

    cout << ans;
}

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

이번에 볼 문제는 백준 2075번 문제인 N번째 큰 수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2075

이 문제의 가장 큰 특징은 메모리 제한이다.

메모리제한이 없다면 시도해볼 수 있는 방법이 많겠지만, 이 문제에서는 모든 N을 입력받아서 보관할 충분한 메모리가 주어지지 않는다.

다행히도, 이 문제에서는 N^2개의 수 가운데 N번째로 큰 수를 구해주기만 하면 된다. 따라서, 수를 하나씩 입력받으면서 가장 큰 수 N개를 계속 관리해나가는 식으로 문제를 해결할 수 있을 것이다.

이를 관리하기 위해 글쓴이는 우선순위 큐(Priority Queue)를 활용하였다.

N+1개의 수가 우선순위 큐에 있는 상태에서 가장 작은 수를 제거할 수 있기 때문이다.

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

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

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

    priority_queue<int> pq;

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        int x; cin >> x;
        pq.push(-x); // min heap으로 활용하기 위한 마이너스 부호
    }

    int NN = N * N;
    for (int i = N;i < NN;i++) {
        int x; cin >> x;
        pq.push(-x); 
        pq.pop();
    }

    cout << -pq.top();
}

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

이번에 볼 문제는 백준 2810번 문제인 컵홀더이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2810

문제 상황에 대한 간단한 관찰을 해보자. 컵홀더가 좌석의 수보다 많은 경우를 제외한다면(모든 좌석이 S인 경우), 가장 많은 개수의 컵홀더를 사용했지만 빈 컵홀더가 남아있는 경우가 존재할 수 있을까?

그러한 경우는 존재하지 않는다. 그 증명은 항상 모든 컵홀더를 사용할 수 있는 방법이 있다는 것을 보이는 방식으로 할 수 있다.

컵홀더의 개수가 좌석의 수 이하이면 LL 좌석이 최소 한번은 등장할 수밖에 없다. 처음 등장하는 LL을 기준으로 1) 왼쪽에 존재하는 컵홀더는 그 컵홀더의 오른쪽에 있는 좌석의 사람이, 2) 오른쪽에 존재하는 컵홀더는 그 컵홀더의 왼쪽에 있는 좌석의 사람이 사용하는 경우, 주어진 좌석에 설치된 모든 컵홀더를 이용할 수 있다.

따라서, 이 문제는 (모든 좌석이 S인 경우를 빼면) 주어진 좌석정보를 보고 컵홀더의 개수를 세는 문제로 바꿔 생각할 수 있다. 이는 전체 N+1개의 컵홀더(모든 좌석이 S인 경우) 가운데 LL의 좌석배치로 인해 놓을 수 없게 된 컵홀더 1개를 제외하는 방식으로 계산할 수 있다.

예제에서 보이듯, SLLLLS와 같은 배치에서 두 커플석 LL과 LL 사이에는 컵홀더가 있음에 유의하자.

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

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

int main()
{
    int N; string s; cin >> N >> s;
    
    int ans = N + 1;
    int cnt = 0;
    for (int i = 0;i < N;i++) {
        if (s[i] == 'L') {
            ans--;
            i++; // 커플석 하나는 LL의 배치를 가지고 있으므로 문자를 두 개 건너뛰기 위함
        }
    }

    if (ans > N) ans = N; // 모든 좌석이 S인 경우
    cout << ans;
}

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

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

www.acmicpc.net/problem/2437

이 문제를 knapsack 문제를 해결하듯이 dp를 이용해서 풀려고 시도할 수는 있겠지만, 이 문제에 하기에는 나올 수 있는 숫자의 범위가 넓어 사용하기 좋은 방법이 아니다.

이 문제에서 요구하는 것은 주어진 추들로 구성하지 못하는 최소 정수이므로, 다음과 같은 과정으로 작은 무게의 추부터 순서대로 살펴보는 것으로 만들 수 없는 가장 작은 무게의 조합을 빠르게 계산해낼 수 있다.

1) 주어진 추 가운데 무게가 1인 추가 없다면 1이 만들 수 없는 가장 작은 무게임은 자명하다.

2) 가장 가벼운 추부터 i번째로 가벼운 추까지 사용하여 만들 수 있는 추의 무게의 범위가 1 이상 K 이하라고 가정하자(i > 0).

2-1) i+1번째로 가벼운 추의 무게 X가 K+1 이하라면, 가장 가벼운 추부터 i+1번째로 가벼운 추까지 사용하여 만들 수 있는 추의 무게의 범위는 1 이상 K+X 이하이다. K의 값을 K+X로 갱신하고, 2)로 돌아가 다음 추를 살펴보자. 다음 추가 없다면 답으로 K+1을 출력하고 프로그램을 종료한다.

2-2) i+1번째로 가벼운 추의 무게 X가 K+1을 넘어간다면, 주어진 추로 K+1이라는 무게를 측정할 수 없음을 알 수 있다. 남은 추의 무게는 모두 K+1을 넘어가기 때문이다. 따라서 답으로 K+1을 출력하고 프로그램을 종료한다.

아래는 제출한 소스코드다. 위의 내용을 그대로 구현한 것으로, 특별한 주석은 달지 않았다.

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

int arr[1000];

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

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        cin >> arr[i];
    }
    
    sort(arr, arr + N);

    if (arr[0] != 1) {
        cout << 1;
        return 0;
    }

    int ans = 1;
    for (int i = 1;i < N;i++) {
        if (arr[i] <= ans + 1) ans += arr[i];
        else break;
    }

    cout << ans + 1;
}

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

이번에 볼 문제는 백준 17481번 문제인 최애 정하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/17481

이 문제는 N명의 "친구들"을 한 묶음으로, 문제에서 주어지는 각 걸그룹 멤버 M명을 한 묶음으로 생각해 이분매칭(maximum bipartite matching) 문제로 풀 수 있다.

각 걸그룹 멤버의 이름이 문자열로 주어지므로, map을 이용해 서로 다른 자연수로 대응시켜주고 이분매칭을 진행하면 간단히 풀 수 있다.

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

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

map<string, int> strtoidx;

vector<int> G[1001];
int visited[1001];
int matching[1001];

int dfs(int current) {
    if (visited[current]) return 0;
    visited[current] = 1;
    for (auto node : G[current]) {
        if (matching[node] == 0) {
            matching[node] = current;
            return 1;
        }
        if (dfs(matching[node])) {
            matching[node] = current;
            return 1;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    for (int i = 1;i <= M;i++) {
        string s; cin >> s;
        strtoidx.insert({ s, i });
    }

    for (int i = 1;i <= N;i++) {
        int K; cin >> K;
        for (int k = 0;k < K;k++) {
            string s; cin >> s;
            G[i].push_back(strtoidx[s]);
        }
    }

    int ans = 0;
    for (int i = 1;i <= N;i++) {
        memset(visited, 0, sizeof(visited));
        ans += dfs(i);
    }

    if (ans == N) cout << "YES";
    else cout << "NO" << '\n' << ans;
}