취미로 코딩하기

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

이번에 볼 문제는 백준 5526번 문제인 ダーツ (Darts)이다.
문제는 아래 링크를 확인하자.

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

네 개 이하의 다트로 얻을 수 있는 점수의 모든 합은 두 개 이하의 다트로 얻을 수 있는 점수의 합 두 개의 조합으로 항상 나타낼 수 있음을 관찰하자.

한편, 다트 하나를 사용하지 않은 것은 가상의 0점 영역에 다트를 던진 것으로 생각해도 결과가 같으므로, 이는 0점 영역을 추가한 후 다트를 항상 2개 사용하는 경우에 대한 문제로 바꿔 생각할 수 있다. 따라서, 위와 같이 변형된 상황에 대하여 두 개의 다트로 얻을 수 있는 점수 조합을 모두 구해둔 뒤, 이분탐색 또는 투포인터로 \(M\) 이하의 가능한 최댓값을 구해 문제를 해결할 수 있다.

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

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

int N, M, idx;
int A[1001001];
int ans;

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> A[i];
	idx = N;
	for (int i = 0; i <= N; i++) {
		for (int j = i; j <= N ;j++) {
			A[++idx] = A[i] + A[j];
		}
	}
	N = idx + 1;
	sort(A, A + N);
	for (int L = 0, R = N - 1; L <= R; 1) {
		if (A[L] + A[R] > M) R--;
		else {
			ans = max(ans, A[L] + A[R]);
			L++;
		}
	}
	cout << ans;
}

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

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

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

범위 내의 육각수의 개수는 800개를 넘지 않는다. 이를 이용하면 범위 내의 각각의 육각수를 이용하여 각 수를 중복해 사용할 수 있는 상황에서의 knapsack dp 문제를 해결하듯이 구현해 문제를 해결하는 것을 시도해 볼 수 있다.

구현을 단순하게 하면 위 연산 과정은 단순한 인덱스 접근 및 사칙연산만으로 이루어져 있으므로 그 실행 속도가 충분히 빠르다. 따라서 잘 구현하면 위의 방법으로도 문제를 충분히 여유롭게 해결할 수 있다.

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

#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <cstring>
using namespace std;

int N;
int sx = 1, g = 1;
int dp[1000001];

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

	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	while (sx < 1000001) {
		for (int i = sx; i < 1000001; i++) dp[i] = min(dp[i], dp[i - sx] + 1);
		g += 4;
		sx += g;
	}

	cin >> N;
	cout << dp[N];
}

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

이번에 볼 문제는 백준 1341번 문제인 사이좋은 형제이다.
문제는 아래 링크를 확인하자.

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

남아있는 케이크를 길이가 \(k\)인 패턴 한번의 시행으로 나누어먹으면 \(\frac{1}{2^k}\)만큼을 남기고 나머지는 합이 \(2^k-1\)인 음이 아닌 두 정수의 비율로 나누어 먹게 됨을 관찰하자. 남은 조각은 같은 패턴으로 계속 반복하여 먹게 되고 그 조각의 크기는 패턴을 반복할 수록 0에 수렴하므로, 이 문제는 주어진 분수의 분모를 (가능한 작은) \(2^k-1\)꼴로 만들어 분자의 이진수 표기에 따라 케이크를 두 사람에게 나누어 주는 것으로 해결할 수 있음을 알 수 있다.

구현에 따라 64비트 정수 자료형을 이용해도 오버플로우가 발생할 수 있으니 유의하자.

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

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

ll AA, BB;
lll A, B;
lll b = 1;
string ans;

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

	cin >> AA >> BB;
	A = AA, B = BB;
	while (b <= 9223372036854775807LL && b % B) {
		b = b * 2 + 1;
	}
	if (b > 9223372036854775807LL) {
		cout << -1;
		return 0;
	}
	A *= b / B;
	while (b) {
		if (A & 1) ans += '*';
		else ans += '-';
		A >>= 1, b >>= 1;
	}
	if (ans.length() > 60) cout << -1;
	else {
		while (!ans.empty()) {
			cout << ans.back();
			ans.pop_back();
		}
	}
}

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

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

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

입력으로 주어지는 수가 0 또는 음의 정수일 수 있다는 점에 유의하자.

주어지는 수에 0이 포함되어 있는 경우, 0이 하나라면 불가능하고 둘 이상이면 항상 가능함을 어렵지 않게 관찰할 수 있다. 아래에서는 주어지는 수에 0이 포함되어있지 않은 경우만을 생각한다.

어떤 한 수와 다른 모든 수의 곱이 같다는 것은 그 하나의 수가 모든 수의 곱의 제곱근과 같아야 함을 관찰할 수 있다. 이 때 제곱근은 양의 제곱근과 음의 제곱근 둘 중 어떤 것이어도 상관없다. 이를 이용하면 풀이를 어렵지 않게 구성할 수 있다.

그러나 모든 수의 곱으로 가능한 값은 매우 크므로 직접 모든 수를 곱하는 것은 매우 느릴 것이다. 이 부분은 어떻게 최적화할 수 있을까? 간단한 방법 중 하나는 주어지는 수의 절댓값이 10억 이하임을 이용하는 것이다. 구체적으로, 이 중 하나의 값이 제곱근이어야 하므로 모든 수의 곱의 절댓값이 10억의 제곱보다 커진다면 주어진 수에서 제곱근을 더 이상 고를 수 없음을 알 수 있다.

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

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

lll prd = 1; ll L, R;
int zcnt; bool WA;

int N;
vector<int> vec;

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

	cin >> N; vec.reserve(N);
	while (N--) {
		int x; cin >> x;
		if (x == 0) {
			zcnt++;
			continue;
		}
		prd *= x;
		if (prd > 1000000000000000000LL || prd < -1000000000000000000LL) WA = 1;
		if (WA) continue;
		vec.emplace_back(x);
	}
	if (zcnt) {
		if (zcnt == 1) cout << "No";
		else {
			cout << "Yes" << '\n';
			cout << 0;
		}
		return 0;
	}
	if (WA || prd < 0) {
		cout << "No";
		return 0;
	}

	L = 1, R = 1000000000; 
	while (L < R) {
		ll mid = (L + R) / 2;
		if (mid * mid < prd) L = mid + 1;
		else R = mid;
	}
	if (L * L != prd) {
		cout << "No";
		return 0;
	}

	for (auto &x:vec) {
		if (abs(x) == L) {
			cout << "Yes\n";
			cout << x;
			return 0;
		}
	}
	cout << "No";
}

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

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

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

공에 적힌 수가 두 가지 이상일 경우 어떤 수를 바꾼다면 양 옆의 수와 다른 수를 항상 골라 그 수로 바꿀 수 있음을 관찰하자. 따라서 이 경우 고른 수를 왼쪽부터 살피면서 같은 수가 적힌 공이 연속으로 있는 지점을 발견할 때마다 오른쪽 공을 양 옆 수와 다른 수를 적어넣는 것으로 최소 횟수의 수정으로 조건을 만족하는 수열을 만들 수 있음을 알 수 있다.

공에 적힌 수가 두 가지뿐인 경우를 생각해 보자. 두 수를 1과 2라고 하면 가능한 수열은 1과 2가 교대로 등장하는 수열 두 가지(1로 시작, 2로 시작)뿐이다. 따라서 이 두 가지 중 어떤 수열로 바꾸는 것이 비용이 덜 드는지를 확인해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, K;
int A[500000];
int cnt1, cnt2;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	if (K == 2) {
		for (int i = 0; i < N; i++) {
			if (i & 1) {
				if (A[i] == 1) cnt1++;
				else cnt2++;
			}
			else {
				if (A[i] == 1) cnt2++;
				else cnt1++;
			}
		}
		cout << min(cnt2, cnt1);
	}
	else {
		int old = 0, ans = 0;
		for (int i = 0; i < N; i++) {
			if (A[i] == old) ans++, old = 0;
			else old = A[i];
		}
		cout << ans;
	}
}

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

이번에 볼 문제는 백준 18066번 문제인 Move & Meet이다.
문제는 아래 링크를 확인하자.

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

먼저, 움직여야하는 총 횟수와 두 점 사이의 거리의 기우성(홀짝)이 다르면 어떻게 움직여도 둘이 같은 위치에 있을 수 없음을 관찰하자. 또한 두 점 사이의 거리보다 움직이는 횟수가 적어도 둘이 같은 위치에 있을 수 없음을 관찰하자.

나머지 경우에는 둘이 같은 위치에 있을 수 있으므로, 한 방향으로 먼저 움직이고 다른 방향으로 이어 움직이는 것을 생각해 문제를 해결하자. 이 때, 기우성에 따라 도착할 수 없는 칸을 도착 지점으로 출력하지 않아야 하는 점에 유의해야 한다.

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

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

ll X, Y, XY, A, B, AB;
ll val;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> X >> Y >> XY >> A >> B >> AB;
	val = abs(X - A) + abs(Y - B);
	if ((val & 1) != ((XY + AB) & 1)) cout << "impossible";
	else if (val > XY + AB) cout << "impossible";
	else {
		if (X > A) swap(X, A), swap(Y, B), swap(XY, AB);
		if (A - X >= XY) cout << X + XY << ' ' << Y;
		else {
			XY -= A - X;
			X = A;
			if ((XY & 1) == (abs(Y - B) & 1)) {
				if (Y > B) cout << X << ' ' << max(Y - XY, B);
				else cout << X << ' ' << min(Y + XY, B);
			}
			else {
				if (Y > B) cout << X << ' ' << max(Y - XY, B + 1);
				else cout << X << ' ' << min(Y + XY, B - 1);
			}
		}
	}
}