취미로 코딩하기

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

이번에 볼 문제는 백준 2623번 문제인 음악프로그램이다.
문제는 아래 링크를 확인하자.

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

주어지는 출연순서 관계들을 하나의 그래프로 나타내고, 위상정렬을 시도한다.

만약 순서를 정할 수 있다면(DAG라면) 그 결과로 "가능한 출연순서" 중 하나를 얻을 것이다.

그렇지 않다면, 그래프에 사이클이 포함되어있으므로 얻은 순서의 크기가 N보다 작게 되고, 이를 확인하여 0을 출력한다.

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

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

vector<int> G[1001];
int cnt[1001];

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

	int N, M; cin >> N >> M;
	while (M--) {
		int K; cin >> K;
		if (K == 0) continue;
		K--;
		int old; cin >> old;
		while (K--) {
			int current; cin >> current;
			G[old].push_back(current);
			cnt[current]++;
			old = current;
		}
	}

	queue<int> que;
	queue<int> ans;

	for (int i = 1; i <= N; i++) {
		if (!cnt[i]) que.push(i);
	}

	while (!que.empty()) {
		int current = que.front(); que.pop();
		ans.push(current);

		for (auto node : G[current]) {
			cnt[node]--;
			if (!cnt[node]) que.push(node);
		}
	}

	if (ans.size() < N) cout << 0;
	else {
		while (!ans.empty()) {
			cout << ans.front() << '\n';
			ans.pop();
		}
	}
}

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

이번에 볼 문제는 백준 12924번 문제인 멋진 숫자 쌍이다.
문제는 아래 링크를 확인하자.

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

주어지는 입력의 크기를 확인하자.

각 범위의 수에 대하여, 모두 한번씩 떼었다 붙여도 충분한 시간이 남을 것 같지 않은가?

가장 많이 확인해봐야 할 100만~200만 범위에서도 약 100만개의 수의 6가지 배치, 약 600만개의 경우의 수만을 조사해보는 것으로 충분히 문제를 해결할 수 있다는 점을 관찰해내면, 남은 것은 구현 뿐이다.

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

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

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

	int L, R; cin >> L >> R;
	int ans = 0;
	for (int i = L; i < R; i++) {
		set<int> st;
		int tmp1 = 10;
		int tmp2 = 1;
		while (tmp2 <= L) tmp2 *= 10;
		tmp2 /= 10;
		while (tmp1 < i) {
			int temp = (i % tmp1) * tmp2 + i / tmp1;
			if (i < temp && temp <= R) {
				if (st.find(temp) == st.end()) {
					st.insert(temp);
					ans++;
				}
			}
			tmp1 *= 10;
			tmp2 /= 10;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 2904번 문제인 수학은 너무 쉬워이다.
문제는 아래 링크를 확인하자.

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

주어진 총 N개의 수를 이루는 각 소인수가 총 몇 개씩 있는지를 구하고, 이를 균일하게 분배하는 것으로 "가장 높은 점수"를 구할 수 있다.

이러한 "가장 높은 점수"를 만들기 위해, 각 칸마다 "부족한 소인수"를 어딘가에 있을 남는 소인수를 옮겨오면(그 수에서 해당 소인수를 나누고 소인수가 부족한 수에 곱하면) 되므로, 각 N개의 수마다 "가장 높은 점수"의 배수가 되기 위해 필요한 소수의 개수를 구해 더한 것이 "가장 높은 점수"를 얻기 위해 필요한 최소 행동 횟수가 된다.

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

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

bool sieve[1000000];
vector<int> primes;
int num[100];
int cnt[1000000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	sieve[0] = sieve[1] = 1;
	for (ll i = 2; i < 1000000; i++) {
		if (sieve[i]) continue;
		primes.push_back(i);
		for (ll j = i * i; j <= 1000000; j += i) {
			sieve[j] = 1;
		}
	}

	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		num[i] = x;
		int idx = 0;
		while (x > 1) {
			if (x % primes[idx] == 0) {
				x /= primes[idx];
				cnt[primes[idx]]++;
			}
			else idx++;
		}
	}
	int ans = 1;
	for (int i = 2; i < 1000000; i++) {
		int temp = cnt[i] / N;
		while (temp--) {
			ans *= i;
		}
	}

	cout << ans << ' ';
	
	int anscnt = 0;
	for (int i = 0; i < N; i++) {
		int x = num[i], y = ans;
		int idx = 0;
		while (y > 1) {
			if (y % primes[idx] == 0) {
				y /= primes[idx];
				if (x % primes[idx] != 0) anscnt++;
				else x /= primes[idx];
			}
			else idx++;
		}
	}

	cout << anscnt;
}

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

이번에 볼 문제는 백준 1193번 문제인 분수찾기이다.
문제는 아래 링크를 확인하자.

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

글쓴이는 분모와 분자의 합을 먼저 구하고, 거기에서 주어진 숫자가 몇 번째인지를 계산하는 방식으로 문제를 해결했다.

대각선의 방향이 번갈아가며 바뀐다는 점에 유의하자. 이는 분모와 분자의 합이 홀수인지 짝수인지를 확인하는 걸로 간단히 확인할 수 있다.

아래는 구현한 소스코드이다.

#include <iostream>
using namespace std;

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

	int N; cin >> N;

	int idx = 1;
	while (idx * (idx + 1) / 2 < N) idx++;
	
	int nth = N - idx * (idx - 1) / 2;

	if (idx & 1) cout << idx - nth + 1 << '/' << nth;
	else cout << nth << '/' << idx - nth + 1;
}

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

이번에 볼 문제는 백준 11729번 문제인 하노이 탑 이동 순서이다.
문제는 아래 링크를 확인하자.

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

하노이 탑 문제는 잘 알려진 유명한 문제이므로 문제에 대한 설명은 생략한다.

탑 A를 B로 옮기려면, A의 바닥을 제외한 나머지를 제 3의 바닥 C로 옮기고 A의 바닥을 B로 옮긴 다음, C에 옮겨둔 탑을 다시 B로 옮기면 된다.

이 과정은 재귀적으로 구현이 가능하다.

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

#include <iostream>
using namespace std;

void hanoi(int N, int A, int B, int C) { // A: 시작위치 B: 도착위치 C: (상대적) 빈칸
	if (N == 1) cout << A << ' ' << B << '\n';
	else {
		hanoi(N - 1, A, C, B);
		cout << A << ' ' << B << '\n';
		hanoi(N - 1, C, B, A);
	}
}

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

	int idx = 1;
	int N; cin >> N;
	for (int i = 1; i < N; i++) {
		idx <<= 1; idx++;
	}
	cout << idx << '\n';
	hanoi(N, 1, 3, 2);
}

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

이번에 볼 문제는 백준 17394번 문제인 핑거 스냅이다.
문제는 아래 링크를 확인하자.

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

BFS를 이용하여 가장 빠르게 목적이 되는 수까지 도달하는 횟수를 세자.

각 숫자에 도달할 때마다 "A이상 B이하 && 이 숫자는 소수" 라는 조건을 만족하는지를 체크하면 된다.

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

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

bool sieve[1000001];
int visited[1000001];

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

	sieve[0] = sieve[1] = 1;

	for (int i = 2; i < 317; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j <= 1000000; j += i) {
			sieve[j] = 1;
		}
	}

	int T; cin >> T;
	while (T--) {
		memset(visited, 0, sizeof(visited));
		queue<int> que;
		int N, A, B; cin >> N >> A >> B;
		que.push(N);
		visited[N] = 1;
		int ans = -1;
		while (!que.empty()) {
			int current = que.front(); que.pop();
			if (A <= current && current <= B && !sieve[current]) {
				ans = visited[current] - 1;
				break;
			}
			if (!visited[current / 2]) {
				visited[current / 2] = visited[current] + 1;
				que.push(current / 2);
			}
			if (!visited[current / 3]) {
				visited[current / 3] = visited[current] + 1;
				que.push(current / 3);
			}
			if (current > 0) {
				if (!visited[current - 1]) {
					visited[current - 1] = visited[current] + 1;
					que.push(current - 1);
				}
			}
			if (current < 100000) {
				if (!visited[current + 1]) {
					visited[current + 1] = visited[current] + 1;
					que.push(current + 1);
				}
			}
		}
		cout << ans << '\n';
	}
}