취미로 코딩하기

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

이번에 볼 문제는 백준 1343번 문제인 폴리오미노이다.
문제는 아래 링크를 확인하자.

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

문제에서 사전순으로 가장 앞서는 답을 출력할 것을 요구하고 있으므로, greedy하게 X 4개가 연속으로 써진 것이 발견되면 A를, 4개를 채우지 못했지만 2개의 X가 연속으로 있고 .이 나왔다면 B를, 홀수개를 채워야 하는 상황이 나오면 -1을 출력해주자.

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

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

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

	string s; cin >> s;
	s.push_back('.');
	int slen = s.length();

	bool chk = 0;
	int cnt = 0;
	int idx = 0;
	while (idx < slen) {
		if (s[idx] == '.') {
			if (cnt == 2) {
				cnt = 0;
				s[idx - 2] = s[idx - 1] = 'B';
			}
			else if (cnt != 0) {
				chk = 1;
				break;
			}
		}
		else {
			cnt++;
			if (cnt == 4) {
				cnt = 0;
				s[idx - 3] = s[idx - 2] = s[idx - 1] = s[idx] = 'A';
			}
		}
		idx++;
	}
	s.pop_back();
	if (chk) cout << -1;
	else cout << s;
}

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

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

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

이 문제는 주어진 길이 2N의 올바른 괄호문자열이 몇개인지 세는 문제이다. (홀수 길이의 괄호문자열은 올바를 수가 없다.)

이러한 괄호문자열의 개수는 N번째 카탈란 수(Catalan Number)와 같다는 것이 잘 알려져있다.

글쓴이는 카탈란 수를 구하는 점화식 중 C_(n+1) = (C_i * C_(n-i) 들의 합, i는 0부터 n까지) 을 이용하여 문제를 해결했다.

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

#include <iostream>
using namespace std;

long long dp[2501];

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

	dp[0] = 1;
	for (int i = 1; i <= 2500; i++) {
		int L = 0, R = i - 1;
		while (L < i) {
			dp[i] += (dp[L++] * dp[R--]) % 1000000007;
		}
		dp[i] %= 1000000007;
	}
	
	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		if (x & 1) cout << 0 << '\n';
		else cout << dp[x >> 1] << '\n';
	}
}

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

이번에 볼 문제는 백준 1670번 문제인 정상 회담 2이다.
문제는 아래 링크를 확인하자.

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

2N명의 대표가 모여있고, 그 중 한 소국가의 대표 A를 정하여 상황을 분석해보자.

이 대표가 어떤 후보와 악수를 하느냐에 따라, 양쪽으로 0 / 2N-2, 2 / 2N-4, 4 / 2N-6, ... , 2N-2 / 0명의 대표들이 있는 상황이 생길 것임을 알 수 있다. (홀수/홀수로 나누어진다면 악수를 하지 못하는 대표들이 생긴다.)

각 상황의 경우를 X / Y 로 나타낸다면, 구하는 경우의 수는 X명의 대표가 악수를 하는 경우의 수와 Y명의 대표가 악수를 하는 경우의 수의 곱들을 모두 합한 것으로 계산할 수 있을 것임을 알 수 있다. (이 점화식을 만족하는 수는 카탈란 수(Catalan Number)임이 잘 알려져있으나, 나누는 수 987654321은 소수가 아니므로 modulo에 대한 역원을 이용한 조합계산을 이용하기는 어렵다.)

위의 점화관계를 이용하여 dp를 하면 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

long long dp[5001];

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

	dp[0] = 1;

	int N; cin >> N;
	N /= 2;

	for (int i = 1; i <= N; i++) {
		int L = 0, R = i - 1;
		while (L < i) {
			dp[i] += (dp[L++] * dp[R--]) % 987654321;
		}
		dp[i] %= 987654321;
	}
	
	cout << dp[N];
}

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

이번에 볼 문제는 백준 1057번 문제인 토너먼트이다.
문제는 아래 링크를 확인하자.

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

이 문제에서는 문제에서 주어진 토너먼트 방식에서 두 사람이 몇 번째 라운드에 만나는지 알아내는 문제이다.

매 라운드마다, k번 참가자가 다음 라운드로 진출한다면 (k+1)/2번 참가번호를 다음에 가진다는 것을 눈여겨보면, 문제에서 주어진 조건 그대로 구현하는 것으로 이 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

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

	int N, x, y; cin >> N >> x >> y;
	int ans = 1;
	while (1) {
		if (x & 1) x++;
		if (y & 1) y++;
		if (x == y) break;
		ans++;
		x >>= 1; y >>= 1;
	}
	cout << ans;
}

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

이번에 볼 문제는 백준 16443번 문제인 Bolinhas de Gude이다.
문제는 아래 링크를 확인하자.

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

하나의 공통된 보드판 위에서 누구의 차례더라도 할 수 있는 움직임이 같으므로 이 게임은 impartial game이고, 따라서 이 문제는 Grundy 수를 이용하여 문제를 해결할 수 있다.

다음과 같이 문제의 상황을 분류하자.

(1) 초기상태에 한번에 (0,0)으로 옮길 수 있는 구슬이 있는 경우 왕이 이긴다.

(2) (1)에 해당하는 구슬이 없는 상황을 생각해보자. 이 때, 각 플레이어는 "(1)에 해당하는 칸으로 말을 움직이지 않는다"는 제약을 갖고 구슬을 움직여야 한다고 가정해도 좋다. (그러한 움직임을 하면 바로 다음 차례에 지기 때문이다.)

이러한 제약사항에서 게임판 위의 각 칸에 대한 grundy 수를 계산할 수 있고, 이를 이용하여 문제를 해결할 수 있다.

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

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

int grundy[101][101];
int tmp[150];

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

    for (int i = 1; i <= 100; i++) {
        for (int j = i + 1; j <= 100; j++) {
            memset(tmp, 0, sizeof(tmp));

            for (int k = 1; k < i; k++) {
                if (k == j) continue;
                tmp[grundy[k][j]] = 1;
            }
            for (int k = 1; k < j; k++) {
                if (k == i) continue;
                tmp[grundy[i][k]] = 1;
            }
            int x = i - 1, y = j - 1;
            while (x > 0 && y > 0) {
                tmp[grundy[x--][y--]] = 1;
            }

            int idx = 0;
            while (tmp[idx]) idx++;
            grundy[i][j] = grundy[j][i] = idx;
        }
    }

    int N; cin >> N;
    bool chk = 0;
    int ans = 0;
    while (N--) {
        int x, y; cin >> x >> y;
        if (x == 0 || y == 0 || x == y) chk = 1;
        ans ^= grundy[x][y];
    }

    if (chk || (ans != 0)) cout << 'Y';
    else cout << 'N';
}

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

이번에 볼 문제는 백준 18250번 문제인 철도 여행이다.
문제는 아래 링크를 확인하자.

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

그래프에서의 오일러 경로(Euler path)에 대한 지식을 묻는 문제이다.

어떤 그래프가 연결그래프일 때 이 그래프가 한붓그리기가 가능하려면 각 꼭짓점의 차수(degree)가 전부 짝수이거나 둘이 홀수여야 한다는 사실은 잘 알려져있다.

만약 차수가 홀수인 꼭짓점이 4개, 6개, ... , 2K개 있다면 이 그래프는 최소 몇 번 선을 그려야할까?

답은 간단하다. 한번의 선 긋기로 차수가 홀수인 꼭짓점을 한번에 최대 2개씩 없앨 수 있다는 점을 생각하면 그 답은 금방 알 수 있을 것이다.

이 문제에서는 조건에서 이 그래프가 연결그래프임을 보장해주지 않았음에 유의하자. 즉, 이 문제에서는 연결된 부분그래프 각각에 대해서 이 그래프를 그리기 위해 선을 몇번 그어야 하는지를 세서 모두 더해주는 방식으로 문제를 해결해야한다.

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

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

int deg[200001];
vector<int> G[200001];
bool visited[200001];

int func(int root) {
	vector<int> stk;
	stk.push_back(root);
	visited[root] = 1;

	int cnt = 0;
	while (!stk.empty()) {
		int current = stk.back();
		stk.pop_back();
		if (deg[current] & 1) cnt++;
		for (auto node : G[current]) {
			if (visited[node]) continue;
			visited[node] = 1;
			stk.push_back(node);
		}
	}
	cnt /= 2;
	if (cnt == 0) return 1;
	else return cnt;
}

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

	int N, M; cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		deg[x]++; deg[y]++;
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (visited[i] || deg[i] == 0) continue;
		ans += func(i);
	}

	cout << ans;
}