취미로 코딩하기

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

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

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

문제의 조건에서, "오민식 그룹이 N명이고, 오민식 그룹의 원래 약속시간이 배열 S라고 하고, 도착하는 시간을 배열A이라고 하고, 약속을 T시간만큼 미뤘다면, 기다리는 시간의 총합은 abs(S[i]+T-A[i])를 모두 더한 값이 된다."라고 한 부분을 주목하자.

S[i] - T[i]는 변하는 값이 아니므로 상수 "-C[i]"로 생각하자. 그러면, 기다리는 시간의 총합은 abs(T-C[i])가 된다.

T가 1 늘어나면 총합은 T>C[i]인 개수만큼 시간의 총합이 늘어나고, T<C[i]인 개수만큼 시간의 총합이 줄어든다.

마찬가지로, T가 1 감소하면 T>C[i]인 개수만큼 시간의 총합이 감소하고, T<C[i]인 개수만큼 시간의 총합이 늘어난다.

위 내용을 잘 생각하면, N이 홀수일 경우 T가 정렬된 C값들 중 중앙값인 경우 하나, 짝수일 경우 정렬된 C값들 중 가운데 두 값 사이(경계값 포함)의 수의 개수가 답이 될 것임을 알 수 있다.

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

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

int arr[10000];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		arr[i] = x - y;
	}
	sort(arr, arr + N);
	if (N & 1) cout << 1;
	else cout << arr[N / 2] - arr[N / 2 - 1] + 1;
}

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

이번에 볼 문제는 백준 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';
	}
}

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

이번에 볼 문제는 백준 11557번 문제인 Yangjojang of The Year이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11557

각 테스트케이스에서, 학교의 이름과 소비한 술의 양이 순서대로 주어질 때, 가장 많은 양의 술을 소비한 학교를 찾으면 되는 문제이다.

가장 많은 양의 술을 소비한 학교만 찾으면 되므로, 학교 이름과 소비한 술의 양을 입력받아 이 술의 양이 기존 최대 술의 양보다 크다면 학교 이름과 소비한 술의 양을 갱신하는 방식으로 문제를 해결할 수 있다.

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

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

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

	int T; cin >> T;
	for (int t = 0; t < T; t++) {
		int N; cin >> N;

		string ans;
		int mx = -1;

		for (int n = 0; n < N; n++) {
			string s; int x; cin >> s >> x;
			if (x > mx) {
				mx = x;
				ans = s;
			}
		}
		cout << ans << '\n';
	}
}

cf. 이 문제에는 위와 같은 풀이가 아닌 번외 풀이(?) 또한 존재한다. 궁금한 사람은 직접 찾아보자.