취미로 코딩하기

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

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

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

문자열을 맨 앞에서부터 작성해나갈 때, a를 지금 썼다고 가정할 시 뒤에 나올 수 있는 문자열의 경우의 수보다 K가 큰지 작은지에 따라 a를 쓸지 z를 쓸지 결정해나갈 수 있다.

사용할 수 있는 z를 모두 썼을 때 K값이 1(a만을 채우는 경우)이 아니라면 이는 가능한 전체 경우의 수보다 K가 크게 주어진 것이므로 -1을 출력한다.

그렇지 않은 경우 문자열을 완성하여 출력한다.

200개 중 100개를 고르는 경우의 수는 64비트 정수 자료형으로도 담을 수 없음에 유의하여 구현하자.

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

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

int comb[201][201];

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

	for (int i = 1; i <= 200; i++) {
		comb[i][0] = comb[i][i] = 1;
	}

	for (int i = 2; i <= 200; i++) {
		for (int j = 1; j < i; j++) {
			comb[i][j] = min(comb[i - 1][j - 1] + comb[i - 1][j], 1000000001);
		}
	}

	string ans = "";
	int N, M, K; cin >> N >> M >> K;
	while (M > 0) {
		if (K > comb[N + M - 1][M]) {
			K -= comb[N + M - 1][M];
			M--;
			ans += "z";
		}
		else {
			N--;
			ans += "a";
		}
	}
	
	if (M == 0) {
		if (K != 1) {
			cout << -1;
			return 0;
		}
	}

	while (N > 0) {
		ans += "a";
		N--;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 13140번 문제인 Hello World!이다.
문제는 아래 링크를 확인하자.

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

이 문제는 hello+world = N을 만족시키는 서로 다른 수를 찾는 복면산 문제이다.

문자가 7종류뿐이므로, 7중 반복문으로 각 문자에 들어갈 수 있는 숫자들을 하나씩 넣어보는 것으로 문제를 해결할 수 있다.

h와 w는 0일 수 없다는 점도 잊지 말고 구현하자.

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

#include <iostream>
using namespace std;

bool visited[10];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N; cin >> N;
	for (int d = 0; d < 10; d++) {
		visited[d] = 1;
		for (int e = 0; e < 10; e++) {
			if (visited[e]) continue;
			visited[e] = 1;
			for (int h = 1; h < 10; h++) {
				if (visited[h]) continue;
				visited[h] = 1;
				for (int l = 0; l < 10; l++) {
					if (visited[l]) continue;
					visited[l] = 1;
					for (int o = 0; o < 10; o++) {
						if (visited[o]) continue;
						visited[o] = 1;
						for (int r = 0; r < 10; r++) {
							if (visited[r]) continue;
							visited[r] = 1;
							for (int w = 1; w < 10; w++) {
								if (visited[w]) continue;
								if (h * 10000 + e * 1000 + l * 120 + o * 1001 + w * 10000 + r * 100 + d == N) {
									cout << "  " << h << e << l << l << o << '\n';
									cout << "+ " << w << o << r << l << d << '\n';
									cout << "-------\n";
									if (N < 100000) cout << "  " << N;
									else cout << ' ' << N;
									return 0;
								}
							}
							visited[r] = 0;
						}
						visited[o] = 0;
					}
					visited[l] = 0;
				}
				visited[h] = 0;
			}
			visited[e] = 0;
		}
		visited[d] = 0;
	}

	cout << "No Answer";
}

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

이번에 볼 문제는 백준 1939번 문제인 중량제한이다.
문제는 아래 링크를 확인하자.

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

글쓴이는 가장 많은 중량을 버틸 수 있는 다리부터 순서대로 다리를 놓아나가다가 두 공장이 같은 component에 있는 때가 오면 그때 놓은 다리가 버틸 수 있는 중량을 출력하는 것으로 문제를 해결했다.

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

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

int uf[10001];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

vector<pair<int, pair<int, int>>> edges;

bool comp(pair<int, pair<int, int>> p1, pair<int, pair<int, int>> p2) {
	return p1 > p2;
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) uf[i] = i;
	for (int i = 0; i < M; i++) {
		int x, y, w; cin >> x >> y >> w;
		edges.push_back({ w,{x,y} });
	}

	sort(edges.begin(), edges.end(), comp);

	int A, B; cin >> A >> B;

	for (auto edge : edges) {
		int x = findf(edge.second.first), y = findf(edge.second.second);
		if (x == y) continue;
		uf[y] = x;
		if (findf(A) == findf(B)) {
			cout << edge.first;
			return 0;
		}
	}
}

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

이번에 볼 문제는 백준 15918번 문제인 랭퍼든 수열쟁이야!!이다.
문제는 아래 링크를 확인하자.

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

랭퍼드 수열(Langford sequence; Langford paring)이란 1과 N까지의 자연수들을 각각 두번씩 사용하여 각 i의 사이에 있는 다른 자연수의 개수가 i개가 되게끔 일렬로 나열한 수열이다. 이 문제는 두 정해진 위치에 같은 수를 이용한 랭퍼드 수열의 개수를 세는 문제이다.

두 정해진 위치에 들어갈 수 있는 같은 수는 유일하다는 점을 관찰하자. 나머지 부분에 들어갈 수는 완전탐색으로 찾는 것으로 충분히 빠르게 문제를 해결할 수 있다.

랭퍼드 수열에 대한 더 많은 내용은 아래의 링크를 참고하자.

https://en.wikipedia.org/wiki/Langford_pairing

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

#include <iostream>
using namespace std;

int N;
int ans = 0;
bool visited[13];
int arr[25];

void func(int idx) {
	if (idx > N) {
		ans++;
		return;
	}
	if (visited[idx]) func(idx + 1);
	else {
		int R = 2 * N - idx - 1;
		for (int i = 1; i <= R; i++) {
			int temp = i + idx + 1;
			if (!arr[i] && !arr[temp]) {
				arr[i] = arr[temp] = idx;
				func(idx + 1);
				arr[i] = arr[temp] = 0;
			}
		}
	}
}

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

	int x, y; cin >> N >> x >> y;
	arr[x] = arr[y] = y - x - 1;
	visited[y - x - 1] = 1;

	func(1);

	cout << ans;
}

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

이번에 볼 문제는 백준 15916번 문제인 가희는 그래플러야!!이다.
문제는 아래 링크를 확인하자.

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

그래프를 이루는 선분 중 (0,0)이 아닌 점에서 y=kx와 만나는 선분이 있다면 그 선분의 한 점은 y=kx의 위쪽, 다른 한 점은 y=kx의 아래쪽에 있어야만 할 것이다.

따라서 y=kx를 기준으로 위쪽 영역 또는 아래쪽 영역에만 점이 찍혀 있다면 F를, 그렇지 않다면 T를 출력하면 된다.

물론, 주어진 점이 y=kx 위에 찍혀있다면 그 또한 당연히 만나는 경우이므로 T를 출력해주자.

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

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

ll arr[100001];

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

	int N; cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	ll K; cin >> K;
	bool chk1 = 0, chk2 = 0;
	for (int i = 1; i <= N; i++) {
		if (arr[i] > K * i) chk1 = 1;
		else if (arr[i] < K * i) chk2 = 1;
		else {
			chk1 = 1, chk2 = 1;
		}
	}

	if (chk1 && chk2) cout << 'T';
	else cout << 'F';
}

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

이번에 볼 문제는 백준 11378번 문제인 열혈강호 4이다.
문제는 아래 링크를 확인하자.

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

아무 직원에게나 적절히 벌점을 분배할 수 있으므로, 정답은 (벌점 없이 일을 최대 하나씩 맡았을 때 가장 많이 할 수 있는 일의 양) 과 K와 (처리가 가능한 일의 양) 둘 중 작은 값이 된다.

직원 1~N 모두가 할줄 모르는 일을 K가 커진다고 처리하게 될 수는 없으니 말이다.

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

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

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

int bipartite(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 (bipartite(matching[node])) {
            matching[node] = current;
            return 1;
        }
    }
    return 0;
}

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

    int cnt = 0;
    int N, M, K; cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        int C; cin >> C;
        while (C--) {
            int x; cin >> x;
            if (!doable[x]) {
                doable[x] = 1;
                cnt++;
            }
            G[i].push_back(x);
        }
    }

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

    cout << min(ans + K, cnt);
}