취미로 코딩하기

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

이번에 볼 문제는 백준 11563번 문제인 연돌이와 고잠녀이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11563

이 문제에서는 서로 교점이 없는 두 선분들의 집합 사이의 최단거리를 구해야 한다.

각 집합의 크기가 최대 2000이므로, 가능한 모든 쌍의 선분(최대 400만쌍)에 대하여 거리를 재는 방식으로 이 문제를 풀 수 있다.

두 선분 AB와 CD 사이의 최단거리는 아래와 같은 후보들 중 하나이다.

1) AC, AD, BC, BD의 길이

2) A에서 CD에 내린 수선, B에서 CD에 내린 수선, C에서 AB에 내린 수선, D에서 AB에 내린 수선의 길이

단, 2에서 해당 수선의 발이 선분의 위가 아닌 연장선상에 있다면 그 값은 후보가 될 수 없다.

점 X에서 선분 YZ에 내린 수선의 발이 선분 위에 있는지 확인하는 방법은 내적을 이용하는 것이다. 구체적으로는 벡터 YX와 YZ의 내적, ZX와 ZY의 내적 값이 각각 양수이면 수선의 발이 선분 위에 있게 된다. (증명은 어렵지 않으므로 생략한다)

점 X와 선분 YZ 사이의 거리는 2 * (삼각형 XYZ의 넓이) / (YZ의 길이) 로 구할 수 있다.

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

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef pair<double, double> pd;

double dist(pd pt1, pd pt2){
	return sqrt((pt1.first - pt2.first) * (pt1.first - pt2.first) + (pt1.second - pt2.second) * (pt1.second - pt2.second));
}

double innerproduct(pd pt1, pd pt2, pd pt3) {
	return (pt2.first - pt1.first) * (pt3.first - pt1.first) + (pt2.second - pt1.second) * (pt3.second - pt1.second);
}

double area(pd pt1, pd pt2, pd pt3) { // 수선길이 = 2 * 넓이 / 밑변길이 이므로 넓이를 구할 때 1/2를 하지 않음
	return abs((pt1.first * pt2.second + pt2.first * pt3.second + pt3.first * pt1.second 
		- pt1.first * pt3.second - pt3.first * pt2.second - pt2.first * pt1.second));
}

double segmentdist(pd pt1, pd pt2, pd pt3, pd pt4) {
	double ret = min(min(dist(pt1, pt3), dist(pt1, pt4)), min(dist(pt2, pt3), dist(pt2, pt4)));
	if (innerproduct(pt1, pt3, pt2) > 0 && innerproduct(pt2, pt3, pt1) > 0)
		ret = min(ret, area(pt1, pt2, pt3) / dist(pt1, pt2));
	if (innerproduct(pt1, pt4, pt2) > 0 && innerproduct(pt2, pt4, pt1) > 0)
		ret = min(ret, area(pt1, pt2, pt4) / dist(pt1, pt2));
	if (innerproduct(pt3, pt1, pt4) > 0 && innerproduct(pt4, pt1, pt3) > 0)
		ret = min(ret, area(pt3, pt4, pt1) / dist(pt3, pt4));
	if (innerproduct(pt3, pt2, pt4) > 0 && innerproduct(pt4, pt2, pt3) > 0)
		ret = min(ret, area(pt3, pt4, pt2) / dist(pt3, pt4));
	return ret;
}

pd sinchon[2000][2];

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

	double ans = 100000;

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		double x, y, z, w; cin >> x >> y >> z >> w;
		sinchon[i][0] = { x,y }, sinchon[i][1] = { z,w };
	}

	for (int j = 0; j < M; j++) {
		double x, y, z, w; cin >> x >> y >> z >> w;
		pd pt3 = { x,y }, pt4 = { z,w };
		for (int i = 0; i < N; i++) {
			ans = min(ans, segmentdist(sinchon[i][0], sinchon[i][1], pt3, pt4));
		}
	}
	cout << fixed;
	cout.precision(10);
	cout << ans;
}

innerproduct(pt1, pt2, pt3): 벡터 pt1pt2와 벡터 pt1pt3의 내적을 계산한다.

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

이번에 볼 문제는 백준 11562번 문제인 백양로 브레이크이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11562

이 문제를 해결하기 위해 먼저 간단한 관찰을 하자.

한 건물에서 다른 건물로 가는 경로는 (일방통행 길을 반대 방향으로 지나가는 경우를 포함하여) 여러 개가 있을 수 있다. 이 문제에서는 이 경로들 중 "일방통행 길을 반대 방향으로 지나가는 횟수"가 최소인 경우의 그 횟수를 구해야한다.

따라서, 일방통행 길을 반대방향으로 지날 때마다 가중치가 1씩 늘어나게 그래프를 만들면 최단경로 알고리즘을 통해 한 점에서 다른 점으로 가는 가장 가중치가 적은 경로와 그때의 가중치(일방통행 길을 반대방향으로 지난 횟수)를 구할 수 있게 된다.

이 문제에서는 여러 쌍의 점에 대하여 질의가 들어오므로, 미리 모든 쌍의 점에 대한 가중치를 계산할 수 있는 Floyd-Warshall(플로이드-워셜) 알고리즘을 이용하는 것이 좋다.

글쓴이 기준으로 이 문제를 dijkstra로 풀어 제출하였을 때에는 864ms, Floyd-Warshall로 풀어 제출하였을 때에는 24ms의 시간이 걸렸다.

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

#include <iostream>
using namespace std;

int dist[251][251];

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

	int N, M; cin >> N >> M;
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = 999;
		}
	}
	for (int i = 1; i <= N; i++) dist[i][i] = 0;

	while (M--) {
		int x, y, z; cin >> x >> y >> z;
		dist[x][y] = 0;
		if (z) dist[y][x] = 0;
		else dist[y][x] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				int temp = dist[i][k] + dist[k][j];
				if (dist[i][j] > temp) dist[i][j] = temp;
			}
		}
	}

	int K; cin >> K;
	while (K--) {
		int s, e; cin >> s >> e;
		cout << dist[s][e] << '\n';
	}
}

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

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

www.acmicpc.net/problem/11561

N이 어떤 수가 오더라도, 징검다리를 주어진 규칙에 맞게 최대한 많이 밟아 건너는 방법 중 하나는 greedy하게 처음서부터 1칸, 2칸, 3칸, ... , n칸과 같이 최대한 적은 칸씩 징검다리를 건너뛰는 것임을 생각할 수 있다. 특히, 마지막 N번째 칸은 꼭 밟아야하므로, X번 칸까지 밟은 뒤에 N번칸으로 뛸 수 없다면 그 X번 칸으로 뛴 점프를 N번 칸으로 바꾸는 점프로 바꿔주는 것으로 최대한 징검다리를 많이 밟아 건너는 경우의 수 중 하나를 찾을 수 있다.

1부터 n까지의 간격의 점프를 한번씩 모두 하여 이동한다면 총 n(n+1)/2칸을 이동하게 되고, n+1까지의 간격의 점프를 한번씩 모두 하여 이동한다면 총 (n+1)(n+2)/2칸을 이동하게 된다.

따라서, 주어진 N에 대하여 n(n+1)/2 <= N < (n+1)(n+2)/2 를 만족하는 N을 찾으면 된다.

이는 각 항에 2를 곱하고 정리하여 간단히 구할 수 있다. 그 이유는 각 항에 2를 곱해 얻은 2N의 범위에서는 제곱수가 (n+1)^2 정확히 하나만 존재하기 때문이다.

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

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

long long arr[231];

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

	int T; cin >> T;
	while (T--) {
		long long N; cin >> N;
		long long ans = sqrt(2 * N);
		if ((ans * ans + ans) / 2 <= N) cout << ans << '\n';
		else cout << ans - 1 << '\n';
	}
}

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

이번에 볼 문제는 백준 11560번 문제인 다항식 게임이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11560

이 문제는 다항식의 전개식에서 계수를 찾을 것을 요구하고 있다.

수의 범위가 충분히 작으므로(곱해지는 다항식의 수가 최대 20개, 나올 수 있는 최대 차수가 210차항), knapsack 문제와 같은 방식의 풀이를 적용해서 문제를 해결할 수 있다.

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

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

long long arr[231];

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

	int T; cin >> T;
	while (T--) {
		memset(arr, 0, sizeof(arr));
		arr[0] = arr[1] = 1;

		int K, N; cin >> K >> N;
		for (int k = 2; k <= K; k++) {
			for (int i = 210; i >= 0; i--) {
				for (int j = 1; j <= k; j++) {
					arr[i + j] += arr[i];
				}
			}
		}
		cout << arr[N] << '\n';
	}
}

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

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

www.acmicpc.net/problem/11559

현재 뿌요뿌요 게임판이 주어졌을 때(단, 뿌요들은 전부 아래로 떨어진 뒤의 상태이다) 총 몇 연쇄를 하게 될지 시뮬레이션을 통해 구하는 문제이다.

이 문제를 해결하기 위해서 글쓴이는 다음과 같은 함수들을 구상하였다.

1) chain 함수

이 함수는 현재의 게임판에서 터질 수 있는 뿌요를 모두 터뜨린다.

다른 말로 하면 chain 함수는 터질 수 있는 뿌요를 모두 "."으로 바꾸는 함수이다.

만약 터뜨린 뿌요가 있다면 1을, 없다면 0을 리턴한다.

이 리턴값은 터뜨린 뿌요가 있다면 연쇄 수를 1 증가시키고 그렇지 않다면 시뮬레이션을 중단시킬 정보로 사용할 수 있다.

보드판에서 터질 수 있는 뿌요를 탐색하는 것은 dfs 또는 bfs등의 탐색으로 각 ('.'이 아닌 게임판 위에서) connected component의 크기를 구하는 것으로 간단히 할 수 있다.

2) drop 함수

이 함수는 막 뿌요가 터진 게임판에서 뿌요를 아래로 떨어뜨리는 함수이다.

글쓴이는 이 함수를 다음과 같이 구현하였다.

2-1) 현재 세로줄에서 바닥으로부터 첫 빈 공간이 나오는 가로줄 A를 찾는다. 없다면 다음 세로줄로 넘어간다.

2-2) 첫 빈 공간으로부터 처음으로 뿌요가 나오는 가로줄 B를 찾는다. 없다면 다음 세로줄로 넘어간다.

2-3) B와 그 위쪽의 뿌요와 빈칸을 그대로 A와 그 위쪽으로 옮긴다.

2-4) 2-1로 돌아간다. (다음 세로줄로 넘어가지 않는다)

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

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

string board[12];
int visited[12][6];
vector<pair<int, int>> puyostk;
vector<pair<int, int>> dfsstk;

void drop() {
	for (int j = 0; j < 6; j++) {
		bool firstblank = 1;
		int i = 0;
		for (; i < 12; i++) {
			if (board[i][j] == '.') {
				firstblank = 0;
				break;
			}
		}
		
		if (firstblank) continue;

		int ii = i + 1;
		bool nextexist = 0;
		for (; ii < 12; ii++) {
			if (board[ii][j] != '.') {
				nextexist = 1;
				break;
			}
		}

		if (!nextexist) continue;
		
		for (; ii < 12; ii++) {
			board[i][j] = board[ii][j];
			board[ii][j] = '.';
			i++;
		}
		j--;
	}
}

int di[4] = { 1,-1,0,0 };
int dj[4] = { 0,0,1,-1 };

void dfs() {
	while (!dfsstk.empty()) {
		auto current = dfsstk.back();
		dfsstk.pop_back();

		int i = current.first;
		int j = current.second;
		puyostk.push_back(current);

		for (int k = 0; k < 4; k++) {
			int ii = i + di[k];
			int jj = j + dj[k];
			if (ii < 0 || ii >= 12 || jj < 0 || jj >= 6) continue;
			if (!visited[ii][jj] && board[ii][jj] == board[i][j]) {
				visited[ii][jj] = 1;
				dfsstk.push_back({ ii,jj });
			}
		}
	}
}

bool chain() {
	bool ret = 0;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (!visited[i][j] && board[i][j] != '.') {
				dfsstk.push_back({ i,j });
				visited[i][j] = 1;
				dfs();
				if (puyostk.size() >= 4) {
					ret = 1;
					for (auto node : puyostk) {
						board[node.first][node.second] = '.';
					}
				}
				puyostk.clear();
			}
		}
	}
	return ret;
}

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

	for (int i = 11; i >= 0; i--) cin >> board[i];

	int ans = 0;
	while (chain()) {
		ans++;
		memset(visited, 0, sizeof(visited));
		drop();
	}

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

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

이번에 볼 문제는 백준 11558번 문제인 The Game of Death이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11558

각 테스트케이스에 해당되는 문제를 간단히 요약하면 다음과 같다.

1) 1부터 N까지의 정수 번호가 붙은 N개의 노드가 있다. 각 노드에는 그 노드를 출발점으로 하는 directed edge가 정확히 하나씩 존재한다. (이 edge는 loop일 수도 있다.)

2) 1번 노드에서 N번 노드까지 가는 최단경로의 길이를 출력한다. 그러한 경로가 없다면 0을 출력한다.

각 노드를 방문할 때마다 다음으로 방문할 수 있는 노드는 오직 하나뿐이므로, 이 문제에서는 그래프를 배열로 구현할 수 있다. visited 배열을 만들어 N을 먼저 방문하면 경로의 길이를, 방문했던 점으로 되돌아오는 경우가 저 발생한다면 0을 리턴한다.

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

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

int G[10001];
int visited[10001];

bool chk = 1;
int cnt = 0;

void dfs(int current, int N) {
	if (current == N) return;
	int next = G[current];
	if (visited[next]) chk = 0;
	else {
		cnt++;
		visited[next] = 1;
		dfs(next, N);
	}
}

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

	int T; cin >> T;
	while (T--) {
		chk = 1;
		cnt = 0;
		memset(visited, 0, sizeof(visited));

		int N; cin >> N;
		for (int i = 1; i <= N; i++) {
			cin>>G[i];
		}
		
		dfs(1, N);

		if (chk) cout << cnt << '\n';
		else cout << 0 << '\n';
	}
}