취미로 코딩하기

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

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

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

a번 컵이 포함된 모음과 b번 컵이 포함된 모음이 서로 다른 경우 a→b와 같은 작업을 하면 두 모음이 하나의 모음으로 합쳐지게 된다. 또한 서로 같은 모음에 들어있을 경우 해당 작업으로 컵의 모음이 변하지 않는다.

각 컵을 노드로 생각하고 a→b 작업을 a번 컵 노드와 b번 컵 노드 사이에 에지를 긋는 것으로 생각해보자. 이 때 a번 컵과 b번 컵이 같은 컵 모음에 들어있는지의 여부는 그래프 위에서 서로 같은 component에 속해있는지의 여부로 생각할 수 있음을 알 수 있다.

위의 관찰을 이용하면 각 a→b 연산에 대응되는 에지를 갖는 그래프에서 가장 큰 두 component에 속한 원소를 하나씩 출력하는 것으로 문제를 해결할 수 있음을 알 수 있다.

해당 그래프가 연결그래프여도(component가 유일하더라도) 유효한 move를 출력해주어야 함에 유의하자.

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

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

int N, M;
vector<int> G[10001];
bool visited[10001];

int dfs(int cur) {
	int ret = 1;
	visited[cur] = 1;
	
	for (auto& nxt : G[cur]) {
		if (visited[nxt]) continue;
		ret += dfs(nxt);
	}

	return ret;
}

int ans1 = 1, cnt1, ans2 = 1, cnt2;

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

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

	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		int cnt = dfs(i);
		if (cnt >= cnt1) {
			ans2 = ans1, cnt2 = cnt1;
			ans1 = i, cnt1 = cnt;
		}
		else if (cnt > cnt2) ans2 = i, cnt2 = cnt;
	}

	cout << ans1 << ' ' << ans2;
}

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

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

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

모든 차의 차량 번호는 다르므로 각 차들을 터널에 들어간 순서대로 0, 1, 2... 과 같이 번호를 붙여 생각할 수 있다.

이 때, 번호 i를 가진 차가 j<i인 번호 j를 가진 어떤 차보다 터널에서 먼저 나온다면 번호 i를 가진 차는 적어도 번호 j를 가진 차를 앞질렀음을 알 수 있다.

N의 범위가 작으므로, 각 번호 i에 대하여 위의 조건을 만족하는 j가 존재하는지를 일일이 반복문을 이용해 찾는 \(O(N^2)\) 알고리즘을 통해 문제를 해결할 수 있다.

아래의 코드는 "터널에서 아직 나오지 않은 가장 작은 차량 번호"를 관리해 효율적(\(O(N)\))으로 문제를 해결한 것이다. 각 차량이 터널에서 나올 때, 해당 차량의 번호가 위의 값보다 크다면 못해도 그 값을 갖는 차량을 추월했을 수밖에 없고, 그렇지 않다면 해당 차량이 그 번호를 갖는 차가 될 수밖에 없음을 관찰해보자.

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

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

int N;
map<string, int> mp;
int visited[1001], idx, cnt;

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));
	}

	while (N--) {
		string s; cin >> s;
		int i = mp[s];
		if (idx < i) cnt++;
		visited[i] = 1;
		while (visited[idx]) idx++;
	}

	cout << cnt;
}

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

이번에 볼 문제는 백준 28294번 문제인 프랙탈이다.
문제는 아래 링크를 확인하자.

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

한 변의 길이가 \(N^a\)인 정\(N\)각형에 문제에서 주어진 작업을 \(k\)번 반복한 도형의, 다음 작업때 변형되는 에지의 개수를 \(e_{N,a}\), 둘레의 길이를 \(l_{N,a}\)라 하자.

이 때 다음 두 식이 성립함을 관찰하자.

\(e_{N,a+1} = (N-1)e_{N,a}\)

\(l_{N,a+1} = (N-2)e_{N,a} + (N-1)l_{N,a}\)

첫 식은 변형되는 에지마다 \(N\)각형 모양이 하나씩 생기는 것을 관찰하는 것으로, 두 번째 식은 먼저 기존 도형을 \(N\)배 확대한 다음 추가되는 길이 \((N-1)e_{N,a}\) 및 지워지는 길이 \(e_{N,a}\)를 관찰하는 것으로 간단히 세울 수 있다.

위 점화관계를 행렬로 표현한 뒤, binary exponentiaion을 이용해 문제의 답 \(l_{N,a}\)을 계산하는 것으로 문제를 해결하자.

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

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

ll N, a;
ll mat[2][2], vec[2];
ll tmp[2][2], vtmp[2];

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

	cin >> N >> a;
	mat[0][0] = N - 1, mat[1][0] = N - 2, mat[1][1] = N, vec[0] = N, vec[1] = N;

	while (a) {
		if (a & 1) {
			vtmp[0] = mat[0][0] * vec[0] + mat[0][1] * vec[1];
			vtmp[1] = mat[1][0] * vec[0] + mat[1][1] * vec[1];
			vec[0] = vtmp[0] % MOD, vec[1] = vtmp[1] % MOD;
		}
		tmp[0][0] = mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0];
		tmp[0][1] = mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1];
		tmp[1][0] = mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0];
		tmp[1][1] = mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1];

		mat[0][0] = tmp[0][0] % MOD;
		mat[0][1] = tmp[0][1] % MOD;
		mat[1][0] = tmp[1][0] % MOD;
		mat[1][1] = tmp[1][1] % MOD;

		a >>= 1;
	}

	cout << vec[1];
}

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

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

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

어떤 양의 정수 \(N\)의 자릿수는 상용로그 \(log_{10}N\)의 지표 + 1과 같이 계산할 수 있음을 상기하자. 이 식을 이용해 문제를 해결할 수 있다.

C++에서 상용로그는 cmath 헤더의 log10 함수를 이용해 간단히 계산할 수 있다. 이 때, 실수 연산의 정밀도를 위해 gcc에서 128비트로 구현된 long double을 이용해주자.

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

#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;

int A, B;

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

	cin >> A >> B;
	cout << (int)(log10((ld)A) * B) + 1;
}

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

이번에 볼 문제는 백준 28291번 문제인 레드스톤이다.
문제는 아래 링크를 확인하자.

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

50x50 배열을 이용해 주어진 레드스톤 회로 블록 배치들을 표현한 뒤, 해당 배열 위에서 회로를 따라 모든 레드스톤 블록으로부터 레드스톤 램프까지 거리 15 이내로 도달할 수 있는지를 판단해 문제를 해결하자. 이는 BFS 등을 이용해 구현할 수 있다.

각 레드스톤 램프는 전기신호를 다시 전달하지 않음에 유의하자.

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

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

int R, C, N;
int board[52][52];
int dist[52][52];
queue<pair<int, int>> que;
int cnt;

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

void bfs() {
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] - 1;
			if (!dist[rr][cc]) continue;
			if (board[rr][cc] == 1) que.push(make_pair(rr, cc));
			else if (board[rr][cc] == 2) board[rr][cc] = 0, cnt--;
		}
	}
}

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

	cin >> C >> R >> N;
	while (N--) {
		string s; int r, c;
		cin >> s >> c >> r;
		r++, c++;

		if (s[9] == 'b') dist[r][c] = 16, que.push(make_pair(r, c));
		else if (s[9] == 'd') board[r][c] = 1;
		else board[r][c] = 2, cnt++;
	}

	bfs();

	if (cnt) cout << "failed";
	else cout << "success";
}

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

이번에 볼 문제는 백준 28292번 문제인 개미 수열이다.
문제는 아래 링크를 확인하자.

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

개미 수열을 이루는 n(>2)번째 문자열을 이용해 n+1번째 문자열을 만드는 과정을 생각해보자. 숫자 a가 n개 연속으로 등장하고 b가 m개 연속으로 등장한다는 의미로 anbm과 같이 문자열을 작성할 때, a와 b는 항상 다르다는 점을 관찰하자. 이 관찰을 이용하면 문제의 답은 3을 넘을 수 없음을 알 수 있다.

또한 이전 문자열에 등장한 숫자 k는 다음 문자열에도 "k가 (k의 개수)개"와 같은 형태로 항상 재등장한다는 점을 관찰하자.

위의 두 관찰과 개미 수열의 앞 몇 항을 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	if (N < 3) cout << 1;
	else if (N < 6) cout << 2;
	else cout << 3;
}