취미로 코딩하기

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

이번에 볼 문제는 백준 20116번 문제인 상자의 균형이다.
문제는 아래 링크를 확인하자.

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

문제가 요구하는 내용을 정리하면, 맨 위의 상자를 제외한 모든 각 상자들에 대하여 해당 상자의 윗면의 범위(경계 미포함) 내부에 그 상자 위로 있는 다른 모든 상자의 \(x\)좌표의 평균이 항상 포함되는지를 판단하는 문제임을 알 수 있다.

위의 상자부터 연속한 각 개수의 상자의 \(x\)좌표의 합을 \(O(n)\)에 먼저 계산해두면 각 상자에 대해 위 조건을 만족하는지 판단을 \(O(n)\)에 어렵지 않게 알 수 있게 된다. 이와 같은 관찰을 이용해 문제를 해결하자.

글쓴이는 위 계산을 유리수 형태로 정리해 부동소수점 자료형 없이 정수 자료형만으로 마쳐 부동소수점 오차 없이 문제를 해결하였다.

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

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

ll N, L;
ll A[200000];
ll total;

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

	cin >> N >> L;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = N - 1, cnt = 1; i > 0; i--, cnt++) {
		total += A[i];
		if (abs(A[i - 1] * cnt - total) >= L * cnt) {
			cout << "unstable";
			return 0;
		}
	}

	cout << "stable";
}

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

이번에 볼 문제는 백준 17251번 문제인 힘 겨루기이다.
문제는 아래 링크를 확인하자.

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

수 \(k\)가 뽑혔을 때 홍팀과 청팀 중 어느 팀이 이기는지(또는 비기는지) 여부는 1번부터 \(k\)번까지의 참가자 중 가장 센 사람과 \(k+1\)번부터 \(N\)번까지의 참가자 중 가장 센 사람의 세기를 비교해 구할 수 있다.

각 \(k\)값에 대해 위의 비교를 모두 하는 것은 1번부터 \(k\)번까지의 참가자 중 가장 센 사람의 세기를 모든 \(k\)에 대해 \(O(N)\)에 먼저 따로 구해두고, 비슷하게 \(N\)번부터 \(k+1\)번까지의 참가자들 중 가장 센 사람의 세기를 모든 \(k\)에 대해 \(O(N)\)에 구해둔다면 총 \(O(N)\)에 구해낼 수 있다.

각각의 \(k\)가 뽑힐 확률이 동일하므로 각 \(k\)값에 대하여 승리하는 경우의 수가 어느 팀이 더 많은지를 위의 방법으로 찾아 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;
int A[1000002];
int L[1000002], R[1000002];
int cntL, cntR;

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) L[i] = max(L[i - 1], A[i]);
	for (int i = N; i > 0; i--) R[i] = max(R[i + 1], A[i]);
	for (int i = 1; i < N; i++) {
		if (L[i] > R[i + 1]) cntL++;
		else if (L[i] < R[i + 1]) cntR++;
	}

	if (cntL > cntR) cout << 'R';
	else if (cntL < cntR) cout << 'B';
	else cout << 'X';
}

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

이번에 볼 문제는 백준 3944번 문제인 나머지 계산이다.
문제는 아래 링크를 확인하자.

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

10진수의 9의 배수 판정법으로 주어진 수의 모든 각 자릿수의 합이 9의 배수인지 확인하는 것이 있다. 이를 배수가 아닌 모든 나머지에 대해, 그리고 2 이상의 모든 진법에 대해 확장해보자.

\(b = B - 1\)이라 할 때, \(B\)진법 수 \(10000000\)은 \(B\)진법 수 \(bbbbbbb + 1\)과 같으므로 \(10000000\)을 \(b\)로 나눈 나머지는 1이 됨을 관찰하자. 이는 꼭 여덟번째 자리에만 해당하는 관찰이 아닌 임의의 자리에 적용될 수 있는 관찰이다.

따라서 \(B\)진법 수를 \(b\)로 나눈 나머지는 각 자리를 나타내는 수의 합을 \(b\)로 나눈 나머지와 같음을 알 수 있다.

위 관찰을 이용해 문제를 해결하자.

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

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

int N; string s;
int total;

void solve() {
	total = 0;
	cin >> N >> s;
	for (auto &l : s) total += l - '0';
	cout << total % (N - 1) << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}

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

이번에 볼 문제는 백준 16400번 문제인 소수 화폐이다.
문제는 아래 링크를 확인하자.

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

\(N\) 이하의 소수들의 합으로 \(N\)을 만드는 경우의 수(더하는 순서는 상관없다)를 구하는 문제이다. 이는 각각의 소수를 제한없이 사용할 수 있는 배낭문제(knapsack)의 일종으로 생각할 수 있다.

40000 이하의 소수는 4203개 존재하며, 40000과 4203의 곱은 168120000이고 이 횟수의 연산은 1초 내에 충분히 빠르게 해낼 수 있다. 특히 knapsack DP의 결과를 구하는 과정에는 단순한 덧뺄셈만이 사용되어 실행시간에 무리가 전혀 가지 않을 것임을 쉽게 예상할 수 있으며, 글쓴이의 풀이는 100ms도 되지 않는 시간에 통과하였다.

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

#include <iostream>
using namespace std;

bool sieve[40001];
void sieveinit() {
	sieve[0] = sieve[1] = 1;
	for (int i = 2; i * i < 40001; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 40001; j += i) sieve[j] = 1;
	}
}

int N;
int dp[40001];

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

	sieveinit();

	dp[0] = 1;
	cin >> N;
	for (int p = 2; p <= N; p++) {
		if (sieve[p]) continue;
		for (int k = p; k <= N; k++) {
			dp[k] += dp[k - p];
			if (dp[k] > 123456788) dp[k] -= 123456789;
		}
	}

	cout << dp[N];
}

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

이번에 볼 문제는 백준 19949번 문제인 영재의 시험이다.
문제는 아래 링크를 확인하자.

https://www.acmcipc.net/problem/19949 

10개의 오지선다 문제의 답을 아무렇게나 찍는 경우의 수는 \(5^{10}\), 즉 9765625가지밖에 되지 않는다.

따라서 가능한 모든 오지선다 답안에 접근해 각각이 영재가 답할 수 있는 답안인지 및 점수가 5점 이상인지를 확인하는 완전탐색으로 이 문제를 해결할 수 있다.

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

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

int A[10];
int pnt, cnt;
vector<int> vec;

void func(int idx) {
    if (vec.size() > 2 && vec[vec.size() - 3] == vec[vec.size() - 2] && vec[vec.size() - 2] == vec.back()) return;
    if (idx == 10) {
        if (pnt > 4) cnt++;
    }
    else {
        for (int i = 1; i < 6; i++) {
            vec.emplace_back(i);
            if (A[idx] == i) pnt++;
            func(idx + 1);
            vec.pop_back();
            if (A[idx] == i) pnt--;
        }
    }
}

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

    for (int i = 0; i < 10; i++) cin >> A[i];
    func(0);
    cout << cnt;
}

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

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

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

0부터 \(2^N-1\)까지의 정수를 비트 수와 크기가 같은 \(2^K\)개의 집합으로 분할하는 문제이다.

0 이상 \(2^N-1\) 이하의 이진수 \(x\)에 대하여 \(x\)와 \(2^N-1-x\)는 \(2^N\)보다 낮은 각 자리에 대하여 대응되는 모든 비트의 상태가 서로 다름을 관찰하자. 따라서 모든 \(x\)와 \(2^N-1-x\)의 쌍은 같은 개수(\(N\)개)의 비트를 포함하게 된다.

주어지는 \(N\)과 \(K\)의 값은 다름이 보장되므로, \(x\)와 \(2^N-1-x\)의 쌍들을 같은 개수로 분배해 \(2^K\)개의 집합을 구성하면 문제의 답 중 하나를 구성할 수 있다. 이를 출력해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, M, K;
int val;

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

	cin >> N >> M;
	N = (1 << N), M = (1 << M);
	K = N / M;
	for (int m = 0; m < M; m++) {
		for (int k = 0; k < K; k += 2) {
			cout << val << ' ' << N - val - 1 << ' ';
			val++;
		}
		cout << '\n';
	}
}