취미로 코딩하기

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

이번에 볼 문제는 백준 17225번 문제인 세훈이의 선물가게이다.
문제는 아래 링크를 확인하자.

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

선물 주문은 많아야 10만개 들어올 수 있고 각 선물은 많아야 300의 시간을 소비해 포장하게 되므로, 길어야 3000만 + (포장시작 시간 상수)정도의 시간 안에 모든 선물의 포장이 완료됨을 알 수 있다.

따라서 시각 1부터 3000만+(상수)까지의 각 시각을 따라 선물 포장 과정을 시뮬레이션하는 것으로 문제를 해결할 수 있다.

반복문으로 구현할 경우, 같은 시각에 여러 선물을 포장할 수 있음에 유의하자.

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

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

int A, B, N;
vector<pair<int, int>> vecA, vecB;
int waitingA, waitingB, cntA, cntB;
vector<int> ansA, ansB;
int gid;

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

	cin >> A >> B >> N;
	while (N--) {
		int t, x; char c; cin >> t >> c >> x;
		if (c == 'B') vecA.emplace_back(make_pair(t, x));
		else vecB.emplace_back(make_pair(t, x));
	}
	sort(vecA.begin(), vecA.end(), greater<>());
	sort(vecB.begin(), vecB.end(), greater<>());

	for (int t = 1; t < 33333333; 1) {
		if (!vecA.empty() && vecA.back().first <= t && waitingA <= t) {
			waitingA = t + A;
			vecA.back().second--;
			if (!vecA.back().second) vecA.pop_back();
			ansA.emplace_back(++gid);
		}
		else if (!vecB.empty() && vecB.back().first <= t && waitingB <= t) {
			waitingB = t + B;
			vecB.back().second--;
			if (!vecB.back().second) vecB.pop_back();
			ansB.emplace_back(++gid);
		}
		else t++;
	}

	cout << ansA.size() << '\n';
	for (auto &x:ansA) cout << x << ' ';
	cout << '\n';
	cout << ansB.size() << '\n';
	for (auto &x:ansB) cout << x << ' ';
}

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

이번에 볼 문제는 백준 30847번 문제인 Нечетный ним이다.
문제는 아래 링크를 확인하자.

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

각 플레이어가 행동을 할 때마다 "돌이 홀수개 남아있는 더미의 개수"의 기우성(홀짝)이 변함을 확인하자. 따라서 각 플레이어는 어떻게 행동하더라도 자신의 턴에 남아있는 "돌이 홀수개 남아있는 더미의 수"의 기우성이 변하지 않음을 관찰할 수 있다.

자신의 턴에 남아있는 돌이 전부 없어진 상태라는 것은 "돌이 홀수개 남아있는 더미의 수"가 짝수인 상태임을 의미한다. 이 내용과 위의 관찰을 토대로 문제를 해결하자.

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

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

ll gcd(ll x, ll y) {
	if (y) return gcd(y, x % y);
	return x;
}

ll N, M, G;
char C;

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

	cin >> N >> M;
	G = min(gcd(N, M), 1000000LL);
	cin >> C;
	while (G--) cout << C;
}

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

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

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

주어진 문자열을 앞부터 차례대로 읽어나가면서, 지금의 문자를 읽었을 때 "START"문자열이 완성되었는지 확인하는 것은 어렵지 않다. 이 때, 이 "START"로 문자열이 완성될 경우의 수는 이 시점까지 완성된 "KICK"의 수와 같음을 관찰하자. 또한 "START"와 "KICK"의 마지막 문자가 서로 다르므로 두 문자열이 동시에 완성되는 경우는 없음을 관찰하자.

위의 관찰을 이용하면, 문자열을 앞부터 읽어나가면서 "START"가 등장할 때마다 지금까지 등장한 "KICK" 부분문자열의 개수를 더하는 것을 반복하는 것으로 문제를 해결할 수 있음을 알 수 있다.

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

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

int N;
string s;

void solve() {
	cin >> s; N = s.length();
	ll ans = 0, kcnt = 0;
	for (int i = 0; i < N; i++) {
		if (i > 3 && s.substr(i - 4, 5) == "START") ans += kcnt;
		else if (i > 2 && s.substr(i - 3, 4) == "KICK") kcnt++;
	}
	cout << ans << '\n';
}

int T;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}

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

이번에 볼 문제는 백준 20917번 문제인 흩날리는 시험지 속에서 내 평점이 느껴진거야이다.
문제는 아래 링크를 확인하자.

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

어떤 고정된 값 \(x\)이 주어질 때 시험지를 \(x\)점 이상의 \(K\)개 그룹으로 나눌 수 있는지 판단하는 것은 그리디한 접근으로 어렵지 않게 해낼 수 있다. 또한 \(x\)의 값이 커질 때 그룹으로 나눌 수 없었다가 나눌 수 있게 되는 경우는 일어날 수 없으며, 마찬가지로 \(x\)의 값이 작아질 때 그룹으로 나눌 수 있었다가 나눌 수 없게 되는 경우는 일어날 수 없다는 점을 관찰할 수 있다.

위의 관찰을 이용하면 문제에서 구하고자하는 점수는 이분탐색을 통해 얻을 수 있음을 알 수 있다.

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

#include <iostream>
using namespace std;

int N, K;
int A[100000];
int L = 0, R = 2000000;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		int cnt = 0, val = 0;
		for (int i = 0; i < N; i++) {
			val += A[i];
			if (val >= mid) cnt++, val = 0;
		}
		if (cnt < K) R = mid - 1;
		else L = mid;
	}

	cout << L;
}

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

이번에 볼 문제는 백준 1940번 문제인 자리수로 나누기이다.
문제는 아래 링크를 확인하자.

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

1, 2, 3, 4, 5, 6, 7, 8, 9의 최소공배수는 2520이다. 따라서 모든 2520의 배수는 0을 제외한 모든 각 자릿수로 나누어떨어짐을 알 수 있다.

위 관찰을 토대로 생각하면, 아무 것도 안 붙이기, 0~9, 00~99, 000~999, 0000~9999를 붙인 수 중에서 답이 항상 존재함을 알아낼 수 있다. 즉, 많아야 11111가지 수(실제로는 이보다 적다. 0000~9999 사이에 적어도 3개의 수는 2520의 배수이기 때문이다.)에 대해 모든 자릿수로 나누어지는지 확인하는 것으로 문제를 해결할 수 있다.

위 내용을 구현한 코드를 작성해 문제를 해결하자.

새로 만들어진 수의 각 자릿수로 나누어떨어지는지를 확인하는 문제가 아님에 유의하자. 즉, 새로 만든 수가 새로 추가된 자릿수로 나누어떨어지는지는 확인하지 않아야 한다.

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

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

string s;
ll N;
vector<ll> dgt;
bool chk(string A) {
	N = stoll(A);
	for (auto &x : dgt) {
		if (N % x) return 0;
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	for (auto &l : s) {
		if (l == '0') continue;
		dgt.emplace_back(l - '0');
	}
	
	if (chk(s)) {
		cout << s;
		return 0;
	}

	for (int i = 0; i < 10; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 1) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
	for (int i = 0; i < 100; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 2) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
	for (int i = 0; i < 1000; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 3) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
	for (int i = 0; i < 10000; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 4) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
}

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

이번에 볼 문제는 백준 20917번 문제인 사회적 거리 두기이다.
문제는 아래 링크를 확인하자.

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

모든 두 좌석 사이의 거리가 \(K\) 이상이 되도록 자리를 고를 때 고를 수 있는 최대 자리 수를 구하는 것은 좌석을 한쪽 끝부터 그리디하게 고르는 전략으로 어렵지 않게 구할 수 있다. 그리고 \(K\)의 값이 커지면 고를 수 있는 자리의 수는 같거나 적어지고, \(K\)의 값이 작아지면 고를 수 있는 자리의 수는 같거나 커진다는 성질을 관찰할 수 있다..

위의 관찰을 이용하면 고를 수 있는 자리의 수가 \(S\) 이상이 되게끔 하는 거리 \(D\)의 범위를 이분탐색을 통해 구할 수 있다. 이를 이용해 문제를 해결하자.

\(X\)값을 활용하기 전 먼저 정렬을 해야 함에 유의해 구현하자.

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

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

int N, S;
int A[200000];
void solve() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);

	int L = 1, R = 999999999;
	while (L < R) {
		int cnt = 0, old = -1000000007;
		int mid = (L + R) / 2 + 1;
		for (int i = 0; i < N; i++) {
			if (A[i] - old >= mid) cnt++, old = A[i];
		}
		if (cnt >= S) L = mid;
		else R = mid - 1;
	}
	cout << L << '\n';
}

int T;

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

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