취미로 코딩하기

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

이번에 볼 문제는 백준 25328번 문제인 문자열 집합 조합하기이다.
문제는 아래 링크를 확인하자.

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

주어지는 각 문자열의 길이는 최대 17임을 확인하자. 즉, 각 문자열은 부분문자열을 많아야 \(2^{17} - 1\)개 존재하며(빈 문자열 제외), 그 중 특정 길이의 문자열만 세면 그 개수는 더욱 적어지고 각 문자열의 길이는 17 이하임을 확인하자. 또한, 주어지는 각 문자열에는 중복된 문자가 존재하지 않으므로 한 문자열에서 조합한 모든 문자열은 서로 다름을 확인하자.

따라서 각 문자열에 대하여 조합 가능한 모든 문자열에 한 번씩 접근해보면서 주어진 세 문자열에서 총 몇 회 등장했는지 기록하는 것으로 문제를 충분히 해결할 수 있다.

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

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

int K;
string X, Y, Z;
string A;
map<string, int> mp;

void func(int idx, string &s) {
	if (A.length() == K) {
		mp[A]++;
		return;
	}
	if (idx == s.length()) return;
	A += s[idx];
	func(idx + 1, s);
	A.pop_back();
	func(idx + 1, s);
}

bool prnt;

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

	cin >> X >> Y >> Z >> K;
	func(0, X); func(0, Y); func(0, Z);
	for (auto &p : mp) {
		if (p.second > 1) cout << p.first << '\n', prnt = 1;
	}
	if (!prnt) cout << -1;
}

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

이번에 볼 문제는 백준 19358번 문제인 Waiter's Problem이다.
문제는 아래 링크를 확인하자.

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

가장 많은 팁을 주는 사람부터 대접하는 것이 항상 최선이다.

\(k\)번째(0-indexed)로 대접한 손님에게 받는 "초기 팁보다 적게 받은 금액"은 \(k\)와 "초기 팁" 두 값중 작은 값과 같다. 이 점을 상기하면 큰 \(k\)값에  작은 "초기 팁" 값을 대응시키는 것이 최적의 전략이 됨을 어렵지 않게 확인할 수 있다. (증명을 원한다면 exchange argument를 활용하자)

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

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

int N;
int A[100000];

void solve() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N, greater<>());
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans += max(A[i] - i, 0);
	}
	cout << ans << '\n';
}

int T;

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

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

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

이번에 볼 문제는 백준 14943번 문제인 벼룩 시장이다.
문제는 아래 링크를 확인하자.

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

각자가 사거나 팔고자 하는 벼룩의 양의 모두 1인 경우를 먼저 생각해보자. 이 경우, 벼룩을 사고자 하는 사람들의 위치와 팔고자 하는 사람들의 위치를 각각 크기순으로 나열하고, 두 위치를 크기순으로 서로 매칭시키는 경우에 비용이 최소가 된다. 증명은 exchange argument로 어렵지 않게 할 수 있다. 또한 같은 논리로 같은 위치에 벼룩을 사거나 팔고자 하는 사람이 여럿 있어도 같은 방식으로 최소 비용을 구할 수 있음을 알 수 있다.

한 사람이 \(A\)마리의 벼룩을 사거나 팔고자 하는 것을 \(A\)명의 사람이 같은 위치에서 각각 한 마리의 벼룩을 사거나 팔고자 하는 것으로 생각해 위의 논리대로 문제를 해결하자. 다만 실제로 마릿수대로 사람을 한명씩 모두 나누어 구현하는 것은 (특히 메모리면에서) 비효율적이므로, 각 사람의 위치 단위로 문제를 해결하자. 이는 투 포인터 기법으로 어렵지 않게 구현 가능하다.

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

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

int N;
vector<pair<int, int>> L, R;
int lsize, rsize, idxL, idxR;
ll ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (x < 0) L.emplace_back(make_pair(-x, i));
		else R.emplace_back(make_pair(x, i));
	}
	lsize = L.size(), rsize = R.size();
	while (idxL < lsize && idxR < rsize) {
		ll val = min(L[idxL].first, R[idxR].first);
		ans += val * abs(L[idxL].second - R[idxR].second);
		L[idxL].first -= val;
		if (!L[idxL].first) idxL++;
		R[idxR].first -= val;
		if (!R[idxR].first) idxR++;
	}
	cout << ans;
}

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

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

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

어떤 에지를 지워서 구하고자 하는 최솟값이 \(K\) 이하가 되게 할 수 있다면 \(K\)보다 더 큰 수 \(K'\) 이하가 되게도 항상 할 수 있고, \(K\) 이하가 되게 할 수 없다면 \(K\)보다 더 작은 수 \(K''\) 이하가 되게 할 수 도 없음을 관찰하자. 따라서 최솟값이 \(K\) 이하가 되게 할 수 있는 K를 이분탐색을 통해 구하는 것을 시도할 수 있다. 그리고 이것이 답이 됨은 어렵지 않게 확인할 수 있다.

어떤 값 \(K\)에 대하여 구하고자 하는 값이 \(K\) 이하인지 확인하는 알고리즘을 구성해보자. 각 두 노드의 쌍 사이에는 두 점을 잇는 두 단순경로가 존재한다. 각 단순경로에 대하여 해당 경로를 구성하는 에지를 하나 지울 시 두 점을 잇는 최단거리는 다른 단순경로의 거리와 같게 되는데, 이 값이 \(K\)보다 크다면 지운 에지를 포함하는 경로에서 에지를 지우면 원하는 결과를 얻을 수 없게 된다. 따라서 이를 통해 두 노드의 쌍에 대하여 지우면 안되는 에지가 무엇인지를 찾을 수 있다.

각 노드의 쌍에 대하여 지울 에지들이 무엇인지 전부 구하고, "지우면 안되는 에지"가 아닌 에지가 존재하는지를 판단하자. 이 과정은 \(O(N + M)\)에 가능하다. imos법을 활용하자.

\(O(N + M)\) 과정을 \(\lg N\)회 반복해 이분탐색을 마치므로, 테스트케이스 하나를 해결하는 데에 드는 시간복잡도는 \(O((N + M)\lg N)\)이 된다.

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

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

int N, M, X[200000], Y[200000];
int A[200002];
bool func(int K) {
	for (int i = 1; i <= N; i++) A[i] = 0;
	for (int k = 0; k < M; k++) {
		int val = Y[k] - X[k];
		if (val > K) A[1]++, A[X[k]]--, A[Y[k]]++;
		if (N - val > K) A[X[k]]++, A[Y[k]]--;
	}
	for (int i = 1; i <= N; i++) {
		A[i] += A[i - 1];
		if (!A[i]) return 1;
	}
	return 0;
}

int L, R;
void solve() {
	L = 0, R = N;
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		if (x > y) swap(x, y);
		if (x == y) {
			i--, M--;
			continue;
		}
		X[i] = x, Y[i] = y;
	}
	while (L < R) {
		int mid = (L + R) / 2;
		if (func(mid)) R = mid;
		else L = mid + 1;
	}
	cout << L << '\n';
}

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

	while (cin >> N >> M) solve();
}

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

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

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

배열을 여러 구간으로 나눴을 때, 어떤 인접한 두 구간의 값의 차가 가장 큰 둘을 남겨두고 다른 부분은 아무렇게나 나누어도 있어도 값의 차의 최댓값이 줄어들지는 않음을 관찰하자. 따라서 전체 구간을 나누는 것을 고려할 필요 없이, 인접한 두 구간의 수의 차가 최대가 되게끔 하는 두 구간을 찾는 것으로 문제를 해결할 수 있다.

어떤 수를 기준으로 인덱스가 감소하는(왼쪽) 방향으로 연속하는 수의 합 중 최대 및 최솟값이 무엇인지, 오른쪽으로는 어떤지를 구하고, 해당 값을 이용해 두 구간이 인접하고 있을 수 있는 모든 위치에 대하여 그곳에서 두 구간이 인접할 때의 값의 최댓값을 모두 살펴 문제를 해결하자. Kadane's algorithm을 이용해 빠르게 필요한 전처리를 할 수 있다.

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

//kadane's algorithm
#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll A[100000];
ll mxL[100000], mnL[100000], mxR[100000], mnR[100000];
ll ans = -1000000000000000000LL;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (ll i = 0, val = 0; i < N; i++) {
		val += A[i];
		mxL[i] = val;
		if (val < 0) val = 0;
	}
	for (ll i = 0, val = 0; i < N; i++) {
		val += A[i];
		mnL[i] = val;
		if (val > 0) val = 0;
	}
	for (ll i = N - 1, val = 0; i > -1; i--) {
		val += A[i];
		mxR[i] = val;
		if (val < 0) val = 0;
	}
	for (ll i = N - 1, val = 0; i > -1; i--) {
		val += A[i];
		mnR[i] = val;
		if (val > 0) val = 0;
	}

	for (int i = 0; i + 1 < N; i++) {
		ans = max(ans, mxL[i] - mnR[i + 1]);
		ans = max(ans, mxR[i + 1] - mnL[i]);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 32046번 문제인 Snacks within 300 Yen이다.
문제는 아래 링크를 확인하자.

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

각 테스트케이스마다, 왼쪽에 있는 과자부터(=주어지는 순서대로) 그 과자를 바구니에 하나를 추가할 수 있는지 여부를 확인하고 바구니에 담거나 담지 않는 것을 반복해 문제를 해결하자. 이는 조건문과 반복문을 이용해 어렵지 않게 구현할 수 있다.

이미 선언한 변수를 테스트케이스마다 반복해서 사용하고자 한다면 그 때마다 해당 변수들을 초기화하고 사용해야 함에 유의하자.

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

#include <iostream>
using namespace std;

int N;

void solve() {
	int ans = 0;
	while (N--) {
		int x; cin >> x;
		if (ans + x < 301) ans += x;
	}
	cout << ans << '\n';
}

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

	cin >> N;
	while (N) {
		solve();
		cin >> N;
	}
}