취미로 코딩하기

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

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

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

어떤 두 양의 정수의 최대공약수가 g이고 최소공배수가 L이라 하자. 이 때 두 정수는 각각 g의 배수이므로 gX, gY와 같이 나타낼 수 있고(단 X와 Y는 서로소) L = gXY와 같이 나타낼 수 있다.

따라서 L/g를 서로소인 두 양의 정수로 나눌 때 두 정수의 합의 최솟값(=X+Y의 최솟값)을 갖는 X와 Y의 값을 구하고 그 값으로 원래의 두 정수 gX와 gY를 출력하는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int A, B, AA, BB;

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

	cin >> A >> B;
	B /= A;
	for (int i = 1; i * i <= B; i++) {
		if (B % i) continue;
		int X = i, Y = B / i;
		if (gcd(X, Y) > 1) continue;

		AA = X, BB = Y;
	}

	cout << A * AA << ' ' << A * BB;
}

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

이번에 볼 문제는 백준 4108번 문제인 지뢰찾기이다.
문제는 아래 링크를 확인하자.

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

각 칸의 인접 지뢰를 세는 배열을 먼저 준비하자. 그리고 각 지뢰칸마다 인접한 8방향의 칸에 인접 지뢰의 개수를 1씩 늘려 지뢰가 아닌 칸의 인접 지뢰 개수를 전부 구하자.

문제의 답은 지뢰칸의 경우 애스터리스크('*')를, 아닌 경우 위에서 구한 인접 지뢰의 개수를 이용해 출력할 수 있다.

아래 구현에서와 같이 dr, dc 등의 배열을 이용하면 8방향의 칸을 살피는 구현을 간략하게 할 수 있다.

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

#include <iostream>
using namespace std;

int R, C;
string board[100];
int ans[100][100];

int dr[8] = { 1,1,1,0,-1,-1,-1,0 };
int dc[8] = { 1,0,-1,-1,-1,0,1,1, };

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

	cin >> R >> C;
	while (R + C) {
		for (int r = 0; r < R; r++) {
			cin >> board[r];
			for (int c = 0; c < C; c++) ans[r][c] = 0;
		}

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r][c] == '*') {
					for (int k = 0; k < 8; k++) {
						int rr = r + dr[k], cc = c + dc[k];
						if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
						ans[rr][cc]++;
					}
				}
			}
		}

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r][c] == '*') cout << '*';
				else cout << ans[r][c];
			}
			cout << '\n';
		}

		cin >> R >> C;
	}
}

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

이번에 볼 문제는 백준 2624번 문제인 동전 바꿔주기이다.
문제는 아래 링크를 확인하자.

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

j번째 동전까지들을 이용해 i원 지폐를 동전들로 환전할 경우의 수를 total[j][i]라 하자. 이 때 j+1에 대한 각 total[j+1][i]의 값은 total[j][i - (j+1번째 동전을 이용해 만들 수 있는 가능한 금액들)]의 합으로 구할 수 있음을 관찰하자.

위에서 관찰한 점화관계를 이용해 dp로 문제를 해결하자.

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

#include <iostream>
using namespace std;

int T, K;
int total[10001];

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

	total[0] = 1;

	cin >> T >> K;
	while (K--) {
		int P, N; cin >> P >> N;
		for (int i = T - 1; i > -1; i--) {
			for (int j = i + P, k = 0; j <= T && k < N; j += P, k++) {
				total[j] += total[i];
			}
		}
	}

	cout << total[T];
}

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

이번에 볼 문제는 백준 3077번 문제인 임진왜란이다.
문제는 아래 링크를 확인하자.

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

첫 줄에 주어지는 해전의 이름들을 차례대로 0, 1, 2, ... , N-1과 대응시키자. 이는 stl의 map을 이용해 간단하게 해낼 수 있다. 그리고 두번째 줄에 주어지는 해전들을 위에서 대응시킨 정수로 나타내자.

이 해전들의 각 쌍을 살펴보며 두 해전의 순서가 올바른지 하나하나 확인하는 것으로 문제를 해결하자. 해전이 일어난 차례대로 0부터 N-1까지의 정수로 이름붙였으므로 두 정수의 대소를 이용해 해전의 순서가 올바른지 검사할 수 있다.

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

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

int N;
map<string, int> mp;
int arr[2500];
int A, B;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		mp.insert(make_pair(s, i));
	}

	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		arr[i] = mp[s];
	}

	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (arr[i] < arr[j]) A++;
			B++;
		}
	}

	cout << A << '/' << B;
}

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

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

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

문제에 따르면 은하 A에서 B까지 이동하는 데에 드는 최소비용은 두 은하 사이의 최단거리의 제곱과 같다.

두 은하 사이의 최단거리는 dijkstra 알고리즘 등을 이용해 간단히 구할 수 있으므로, dijkstra를 n번 돌려 각 사람들로부터 각 은하에 도달하는 비용들을 구하고 이들을 누적해 각 테스트케이스의 답을 구하자. n이 클 경우 floyd-warshall이 더 효율적일 수 있으나 주어지는 입력의 크기가 매우 작으므로 무엇을 사용해도 상관없을 것이다.

n명의 사람들이 항상 만날 수 있는 입력만 주어지지만, n명의 사람들이 방문할 수 없는 은하가 입력에 존재할 수는 있다. 해당 은하를 답의 후보로 생각하지 않도록 구현에 유의하자. 글쓴이는 그런 은하의 경우 거리를 무한대(아래 구현에서는 1,000,000,000,000,000,007)로 취급해주었다.

또한 각 은하에 도달하는 비용의 누적값은 32비트 정수 자료형으로 저장하지 못하는 큰 수가 나올 수 있음에 유의하자.

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

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

int T, P;
vector<pair<int, int>> G[101];
priority_queue<pair<int, int>> pq;
ll total[101];

void dijkstra(int x) {
	vector<int> dist(P + 1);
	dist[x] = 1;
	pq.push(make_pair(-1, x));

	while (!pq.empty()) {
		int d = -pq.top().first, cur = pq.top().second; pq.pop();
		if (dist[cur] < d) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first, dd = p.second;
			if (!dist[nxt] || d + dd < dist[nxt]) {
				dist[nxt] = d + dd;
				pq.push(make_pair(-(d + dd), nxt));
			}
		}
	}

	for (int i = 1; i <= P; i++) {
		if (dist[i]) total[i] += (dist[i] - 1) * (dist[i] - 1);
		else total[i] = 1000000000000000007LL; 
	}
}

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

	cin >> T;
	while (T--) {
		int N, Q; cin >> N >> P >> Q;
		for (int i = 1; i <= P; i++) G[i].clear(), total[i] = 0;
		vector<int> pp(N);
		for (int i = 0; i < N; i++) cin >> pp[i];
		while (Q--) {
			int x, y, d; cin >> x >> y >> d;
			G[x].emplace_back(make_pair(y, d));
			G[y].emplace_back(make_pair(x, d));
		}

		for (auto& x : pp) dijkstra(x);

		int ans = -1; ll ansd = 1000000000000000006LL;
		for (int i = 1; i <= P; i++) {
			if (total[i] < ansd) ansd = total[i], ans = i;
		}

		cout << ans << ' ' << ansd << '\n';
	}
}

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

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

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

사다리 선을 하나 긋는 것은 인접한 두 원소의 차례를 서로 바꾸는 것과 같음을 알 수 있다.

위의 관찰과 함께 사다리의 위아래를 뒤집어 문제를 재해석하면, 주어진 배열을 버블정렬(bubble sort)할 때 필요한 최소 swap 횟수를 구하는 문제로 생각할 수 있다. 이 값을 계산해 문제를 해결하자.

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

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

int T, N;
int arr[1001];

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

	cin >> T;
	while (T--) {
		memset(arr, 0, sizeof(arr));
		int ans = 0;
		cin >> N;
		for (int i = 0; i < N; i++) {
			int x; cin >> x;
			for (int j = x + 1; j <= N; j++) ans += arr[j];
			arr[x] = 1;
		}

		cout << ans << '\n';
	}
}