취미로 코딩하기

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

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

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

구간 땅이 융기하면, 땅이 융기하는 구간의 경계에서의 바람의 온도 변화값만 변하고 나머지 위치에서의 바람의 온도 변화값은 변하지 않는다는 점을 눈치챈다면, 매 쿼리마다 해당 경계의 값만을 계산하는 것으로 문제를 해결할 수 있다.

기존 높이차이때문에 발생하는 온도 차이를 없는 것으로 하고 높이 변화량을 적용한 뒤 새로운 높이차이때문에 발생하는 온도 차이를 다시 계산하는 것으로 최종 온도변화를 쉽게 계산할 수 있다.

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

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

ll old;
ll diff[200001];
ll ans = 0;

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

	int N, Q; ll S, T; cin >> N >> Q >> S >> T;
	cin >> old;
	for (int i = 1; i <= N; i++) {
		ll x = old, y; cin >> y;
		if (x < y) ans -= (y - x) * S;
		else ans += (x - y) * T;
		diff[i] = y - x;
		old = y;
	}

	while (Q--) {
		int L, R; ll d; cin >> L >> R >> d;
		if (L > 0) {
			if (diff[L] > 0) ans += diff[L] * S;
			else ans += diff[L] * T;
			diff[L] += d;
			if (diff[L] > 0) ans -= diff[L] * S;
			else ans -= diff[L] * T;
		}
		if (R < N) {
			R++;
			if (diff[R] > 0) ans += diff[R] * S;
			else ans += diff[R] * T;
			diff[R] -= d;
			if (diff[R] > 0) ans -= diff[R] * S;
			else ans -= diff[R] * T;
		}

		cout << ans << '\n';
	}
}

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

이번에 볼 문제는 백준 8986번 문제인 전봇대이다.
문제는 아래 링크를 확인하자.

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

전봇대의 개수를 N이라 하자.

함수 f(x)를 각 인접한 전봇대 사이 간격을 x로 만들 때의 전봇대 이동 거리로 정의하자.

이것은 |xi-x*i| (0<i<N)들의 합과 같다.

각 |xi-x*i|는 아래로 볼록한 그래프이고, 아래로 볼록한 함수의 합은 다시 아래로 볼록한 함수가 되므로, 주어진 함수는 아래로 볼록한 함수이다.

따라서, 다음과 같은 방식으로 x값을 이분탐색(binary search)을 하면 f(x)가 최소가 되게 하는 x값을 구할 수 있다:

이분탐색을 하는 구간 [L,R]의 새로운 mid값에 대하여, f(mid) <= f(mid+1)라면 찾는 x값은 [L,mid]에서 꼭 찾을 수 있고, 그렇지 않다면 [mid+1,R] 구간에서 꼭 찾을 수 있다.

또는 삼분탐색(ternary search)을 해도 문제를 해결할 수 있을 것이다.

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

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

ll N;
ll arr[100000];

ll func(ll x) {
	ll ret = 0;
	for (ll i = 1; i < N; i++) {
		ret += abs(arr[i] - i * x);
	}
	return ret;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	ll L = 0, R = 1000000000;
	while (L < R) {
		ll mid = (L + R) / 2;
		ll midval = func(mid);
		ll rightval = func(mid + 1);
		if (midval <= rightval) R = mid;
		else L = mid + 1;
	}

	cout << func(L);
}

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

이번에 볼 문제는 백준 15809번 문제인 전국시대이다.
문제는 아래 링크를 확인하자.

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

문제에서 출력해야하는 내용을 잘 살펴보면 "서로 다른 나라들을 규칙에 따라 합쳐나가는" 시행을 빠르게 할 수 있는 disjoint set(union-find) 자료구조를 이용하여 문제를 해결할 수 있을 것임을 짐작할 수 있다.

나라를 합쳐나가면서, 나라의 인구 또한 쿼리에 맞게 같이 조절해나가는 것으로 문제를 해결하자.

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

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

int uf[100001];
int popul[100001];

int findf(int x) {
	if (uf[x] == x) return x;
	return uf[x] = findf(uf[x]);
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> popul[i];
	for (int i = 1; i <= N; i++) uf[i] = i;

	while (M--) {
		int x, a, b; cin >> x >> a >> b;
		a = findf(a), b = findf(b);
		if (x == 1) {
			popul[a] += popul[b];
			popul[b] = 0;
			uf[b] = a;
		}
		else {
			if (popul[a] == popul[b]) popul[a] = popul[b] = 0;
			else {
				if (popul[a] < popul[b]) swap(a, b);
				popul[a] -= popul[b];
				popul[b] = 0;
				uf[b] = a;
			}
		}
	}

	vector<int> ans;
	for (int i = 1; i <= N; i++) {
		if (popul[i]) ans.push_back(popul[i]);
	}

	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (auto a : ans) cout << a << ' ';
}

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

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

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

BOJ#1011의 아이디어를 응용하여 해결할 수 있는 문제이다.

이동하는 데에 사용할 시간을 T라고 하자.

T가 커질 수록 그 시간동안 이동할 수 있는 총 거리는 증가하므로, 가능한 전체 시간의 범위를 두고 이진탐색(binary search)를 통해 T를 찾는 방법을 시도할 수 있다.

다만 T를 직접 변수로 이용하면 식을 세우기 쉽지 않으므로, 글쓴이는 "도달한 최고 속도"를 기준으로 그 때 이동할 수 있는 거리를 구해 이진탐색을 진행했다.

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

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

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

	ll dist, Q; cin >> dist >> Q;
	while (Q--) {
		ll K; cin >> K;
		if (K * (K + 1) / 2 >= dist) {
			ll L = 1, R = K;
			while (L < R) {
				ll mid = (L + R) / 2;
				if (mid * (mid + 1) / 2 >= dist) R = mid;
				else L = mid + 1;
			}
			cout << L << '\n';
		}
		else {
			ll KK = K * (K - 1) / 2;
			ll L = K, R = 100000;
			while (L < R) {
				ll mid = (L + R) / 2;
				if (mid * mid - KK >= dist) R = mid;
				else L = mid + 1;
			}
			if (L * (L - 1) - KK >= dist) cout << 2 * L - K - 1 << '\n';
			else cout << 2 * L - K << '\n';
		}
	}
}

(2022-04-15 수정)

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

이번에 볼 문제는 백준 12722번 문제인 Mousetrap (Large)이다.
문제는 아래 링크를 확인하자.

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

단순히 시뮬레이션을 돌려 카드의 배치를 찾아내는 방식으로 이 문제를 해결하고 싶다면 Small 버전의 문제를 풀도록 하자.

글쓴이는 BOJ#1168를 풀면서 익힌 아이디어를 이용하여 이 문제를 해결했다.

1부터 N까지의 카드를 크기 N의 배열로 나타내고, 각 카드가 현재 남아있으면 1, 없으면 0을 채우자.

그리고 마지막으로 확인했던 지점에서부터 k번째의 카드를 찾아 제거하는 작업을 반복해야한다.

이는 구간합을 다루는 세그먼트트리를 이용하여 관리할 수 있다.

비효율적인 구현을 줄여 시간제한에 걸리지 않도록 신경쓰자.

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

#include <iostream>
using namespace std;

int arr[1000001];
int seg[2097153];
int old;

int init(int L, int R, int sI) {
	if (L == R) return seg[sI] = 1;
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void update(int L, int R, int qVal, int idx) {
	int sI = 1;
	while (L < R) {
		seg[sI]--;
		if (seg[sI * 2] >= qVal) {
			R = (L + R) / 2;
			sI = sI * 2;
		}
		else {
			qVal -= seg[sI * 2];
			L = (L + R) / 2 + 1;
			sI = sI * 2 + 1;
		}
	}
	seg[sI]--;
	arr[L] = idx;
	old = L;
}

int rangesum(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

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

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		old = 0;
		int N; cin >> N;
		init(1, N, 1);
		for (int i = 1; i <= N; i++) {
			int rest = rangesum(1, N, old + 1, N, 1);
			if (rest >= i) update(1, N, rangesum(1, N, 1, old, 1) + i, i);
			else {
				int num = (i - rest - 1) % seg[1] + 1;
				update(1, N, num, i);
			}
		}
		
		int K; cin >> K;
		cout << "Case #" << t << ": ";
		while (K--) {
			int x; cin >> x; cout << arr[x] << ' ';
		}
		cout << '\n';
	}
}

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

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

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

K가 너무 커 숫자를 직접 더하는 것은 (큰 수의 연산을 구현하지 않는 이상) 무리이다.

먼저 간단히 규칙을 찾아보면

1자리 이하의 합: 1(10) = 1(2)

2자리 이하의 합: 6(10) = 110(2)

3자리 이하의 합: 28(10) = 11100(2)

4자리 이하의 합: 120(10) = 1111000(2)

...

임을 알 수 있다.

자릿수 K가 주어졌을 때 출력해야하는 이진수가 무엇인지 규칙이 보이는 것 같다. 그 규칙이 실제로 맞는지의 증명은 각 K에 대하여 1부터 (2^K)-1까지의 수의 합을 계산해낸 후 비교하는 것으로 간단히 할 수 있다.

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

#include <iostream>
using namespace std;

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

	int K; cin >> K;
	for (int i = 0; i < K; i++) cout << '1';
	for (int i = 1; i < K; i++) cout << '0';
}