취미로 코딩하기

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

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

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

두 문자열이 주어질 때, 첫 번째 문자열에 등장한 문자만으로 두 번째 문자열이 구성되어있는지 확인하는 문제이다.

첫 번째 문자열에서의 각 문자의 등장 여부를 저장해둔 배열을 구성하고, 이를 이용해 두 번째 문자열의 각 문자가 첫 번째 문자열에 등장했는지를 판단해 문제를 해결하자.

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

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

string s;
int visited[128];

void solve() {
	memset(visited, 0, sizeof(visited));
	cin >> s;
	for (auto &l:s) visited[l] = 1;
	cin >> s;
	for (auto &l:s) {
		if (!visited[l]) {
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}

int T;

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

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

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

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

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

각 스킬에 대하여, \([L,R]\)에 포함된 스킬 시전 시간을 구해 그 시간과 단위시간당 damage를 곱해 문제를 해결하자.

\([L,R]\)에 포함된 스킬 시전 시간은 \([0,R]\)에 포함된 스킬 시전 시간에서 \([0,L]\)에 포함된 스킬 시전 시간을 빼는 것으로 편하게 계산할 수 있다.

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

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

ll N, S, E;
ld ans;

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

	cin >> N >> S >> E;
	while (N--) {
		ll x, y, t, z; cin >> x >> y >> z;
		ans += (E / (x + y)) * z;
		t = max(0LL, E % (x + y) - x);
		ans += (ld)t / y * z;
		ans -= (S / (x + y)) * z;
		t = max(0LL, S % (x + y) - x);
		ans -= (ld)t / y * z;
	}

	cout << fixed;
	cout.precision(12);
	cout << ans / (E - S);
}

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

이번에 볼 문제는 백준 32685번 문제인 4-LSB이다.
문제는 아래 링크를 확인하자.

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

어떤 자료의 마지막 4-LSB는 이진수 1111(십진수로는 15가 된다)을 and하여 빠르게 구할 수 있다.

이를 이용해 각 수의 4-LSB를 계산하여 문제의 답을 구하자.

leading zero의 개수를 적절히 채워야 함에 유의하자.

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

#include <iostream>
using namespace std;

int A, B, C;
int ans;

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

	cin >> A >> B >> C;
	ans = (A & 15) * 256 + (B & 15) * 16 + (C & 15);
	if (ans < 1000) cout << 0;
	if (ans < 100) cout << 0;
	if (ans < 10) cout << 0;
	cout << ans;
}

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

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

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

Juta가 문제에서 주어진 제한대로 움직이면 세 수 중 첫 번째 수는 1 또는 3, 두 번째 수는 6 또는 8, 세 번째 수는 2 또는 5여야 한다.

각 세 수를 비교하여 하나에서라도 그 외의 수가 주어진다면 "EI"를, 그렇지 않다면 "JAH"를 출력해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	if (N != 1 && N != 3) {
		cout << "EI";
		return 0;
	}
	cin >> N;
	if (N != 6 && N != 8) {
		cout << "EI";
		return 0;
	}
	cin >> N;
	if (N != 2 && N != 5) {
		cout << "EI";
		return 0;
	}
	cout << "JAH";
}

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

이번에 볼 문제는 백준 32674번 문제인 Palindromic Word Search이다.
문제는 아래 링크를 확인하자.

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

직사각형 영역의 임의의 행과 열을 하나씩 고르면 고른 행과 열에 공통으로 속한 칸이 항상 존재한다. (좌표의 원리를 생각하자.) 따라서, 임의의 직사각형 영역에 문제의 조건을 만족하는 행방향의 팰린드롬과 열방향의 팰린드롬이 하나씩 있다면 그 둘을 모두 포함하는 어떤 칸이 항상 존재한다.

따라서 이 문제는 각 칸을 지나는 행방향 팰린드롬의 길이의 최댓값과 열방향 팰린드롬의 길이의 최댓값을 모두 구해 각 칸을 교점으로 하는 직사각형의 넓이의 최댓값을 구하는 것으로 해결할 수 있다.

하나의 행 또는 열에 대하여, 각 문자(또는 두 문자 사이)를 중심으로 하는 팰린드롬의 길이의 최댓값은 manacher 알고리즘 등을 이용해 빠르게 구할 수 있고, sweeping을 통해 각 행 또는 열의 칸에 대하여 그 칸을 포함하는 해당 방향 팰린드롬의 길이의 최댓값을 구해낼 수 있다.

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

// 찾는 사각형은 공통된 칸이 있고,
// 해당 칸 포함 가로 팰린드롬 최대 길이와 세로 팰린드롬 최대 길이를 각각 전처리해서
// 모든 칸에 대해 계산 시도
#include <iostream>
#include <queue>
using namespace std;

int R, C, ans;
char board[500][500];
int valR[500][500], valC[500][500];
string s;
int dp[1001];

void manacher(string& S) {
	int N = S.length();
	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<>> pq1;
	pq1.push(make_pair(make_pair(0, 0), 0));
	dp[0] = 0;
	for (int c = 0, i = 1; i < N; i++) {
		if (i <= c + dp[c]) dp[i] = min(dp[c - (i - c)], (c + dp[c]) - i);
		else dp[i] = 0;
		while (-1 < i - dp[i] - 1 && i + dp[i] + 1 < N && S[i - dp[i] - 1] == S[i + dp[i] + 1]) dp[i]++;
		if (c + dp[c] < i + dp[i]) c = i;
		pq1.push(make_pair(make_pair(i - dp[i], i + dp[i]), dp[i]));
	}
	priority_queue<pair<int, int>> pq2;
	for (int i = 0; i < N; i++) {
		while (!pq1.empty() && pq1.top().first.first == i) {
			pq2.push(make_pair(pq1.top().second, pq1.top().first.second));
			pq1.pop();
		}
		while (pq2.top().second < i) pq2.pop();
		dp[i] = pq2.top().first;
	}
}

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

	s.reserve(1001);
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		s.clear();
		s += '#';
		for (int c = 0; c < C; c++) {
			s += board[r][c];
			s += '#';
		}
		manacher(s);
		for (int c = 0; c < C; c++) valR[r][c] = dp[c * 2 + 1];
	}

	for (int c = 0; c < C; c++) {
		s.clear();
		s += '#';
		for (int r = 0; r < R; r++) {
			s += board[r][c];
			s += '#';
		}
		manacher(s);
		for (int r = 0; r < R; r++) valC[r][c] = dp[r * 2 + 1];
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			ans = max(ans, valR[r][c] * valC[r][c]);
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 32628번 문제인 두 스택이다.
문제는 아래 링크를 확인하자.

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

위에서부터 총 \(K\)개의 물건을 들어 없애는 방법의 수는 한 스택에서 0, 1, \(\cdots\), \(K\)개의 물건을 들어내고 다른 스택에서 \(K\), \(K-1\), \(\cdots\), 1, 0개의 물건을 들어내는 방법 중 실제로 실현이 가능한 것(각 스택에서 들어내는 물건의 개수가 \(N\) 이하인 것)의 수와 같다. 이는 최대 \(K+1\)가지이다.

따라서 prefix sum으로 각 스택의 밑에서부터의 물건의 수를 미리 전처리해 두고 최대 \(K+1\)가지의 모든 경우에 대하여 원빈이가 들어야하는 물건의 값을 각각 조사해 그 중 최솟값을 구하는 것으로 문제를 선형시간에 해결할 수 있다.

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

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

int N, K; ll ans = 2000000000000000007LL;
ll A[100001], B[100001];

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		A[i] += A[i - 1];
	}
	for (int i = 1; i <= N; i++) {
		cin >> B[i];
		B[i] += B[i - 1];
	}

	for (int i = 0; i <= N; i++) {
		int j = (N * 2 - K) - i;
		if (j < 0 || j > N) continue;
		ans = min(ans, max(A[i], B[j]));
	}
	cout << ans;
}