2024-03-15

-회문(17609, 백준)

 문자 하나를 수정해서 회문을 만들 수 있다면, 이를 유사회문이라 부른다. 이때 주어진 문자열이 유사회문인지, 회문인지, 둘 다 아닌지를 판단해야 되는 문제이다. 간단하게 문자열의 앞 뒤를 투포인터로 잡아준 뒤, 검사하다가 서로 다른 문자가 나온다면, 둘중 하나의 포인터를 옮기고 check를 해준다. 이때 이미 check가 되어있다면, 2번이상 바꾸어야 함으로 유사회문이 아니게 되기때문에 break해준다. 재귀로 구현하는 편이 좋다. 하지만 나는 멍청하기 때문에 다른 문자가 나왔을때, 스킵하는 포인터의 우선순위를 왼쪽과 오른쪽을 둘다 구현해서 풀었다.

<소스 코드>

#include <stdio.h>
#include <string.h>

int main()
{
	int i, j, t;
	scanf("%d", &t);
	while (t--) {
		char s[100010];
		int l;
		scanf("%s", s);
		l = strlen(s);
		int check = 0;
		int st = 0, ed = l - 1;
		while (st < ed) {
			if (s[st] != s[ed]) {
				if (s[st + 1] == s[ed]) {
					st++;
					if (check == 1) {
						check = 2;
						break;
					}
					check = 1;
				}
				else if (s[st] == s[ed - 1]) {
					ed--;
					if (check == 1) {
						check = 2;
						break;
					}
					check = 1;
				}
				else {
					check = 2;
					break;
				}
			}
			st++;
			ed--;
		}
		int check2 = 0;
		st = 0, ed = l - 1;
		while (st < ed) {
			if (s[st] != s[ed]) {
				if (s[st] == s[ed - 1]) {
					ed--;
					if (check2 == 1) {
						check2 = 2;
						break;
					}
					check2 = 1;
				}
				else if (s[st + 1] == s[ed]) {
					st++;
					if (check2 == 1) {
						check2 = 2;
						break;
					}
					check2 = 1;
				}
				else {
					check2 = 2;
					break;
				}
			}
			st++;
			ed--;
		}
		if (check == 1 || check2 == 1) check = 1;
		printf("%d\n", check);
	}
	return 0;
}

-우체국(2141, 백준)

 직관적으로 보이길래 증명없이 풀었다. "양옆의 사람수의 차이가 최소인 지점이 항상 우체의 지점이 된다"를 코딩으로 구현하면 된다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

long long n;
long long sum, L, R;
vector <pair<long long, long long>> vec;
long long ans = 2e19;
long long ans_idx;

int main()
{
	long long i, j;
	scanf("%lld", &n);
	for (i = 0; i < n; i++) {
		long long x, y;
		scanf("%lld %lld", &x, &y);
		vec.push_back({ x, y });
		sum += y;
	}
	sort(vec.begin(), vec.end());
	for (i = 0; i < n; i++) {
		R = sum - L - vec[i].second;
		long long res = abs(R - L);
		if (res < ans) ans = res, ans_idx = i;
		L += vec[i].second;
	}
	ans_idx = vec[ans_idx].first;
	printf("%lld", ans_idx);
	return 0;
}

-확장 게임(16920, 백준)

 BFS응용 문제이다. 플레이어가 순서대로 턴을 씀으로, 턴을 쓰고 끝나는 지점을 다음번에 검사하기 위해 따로 큐에 담아두었다 다음에 자신의 차례가 왔을 때, 꺼내서 탐색하면 된다. 이때, 3중반복문을 사용하면 시간 초과가 나오게 됨으로, 여러 턴을 한번에 쓰는 경우를 잘 처리해 주어야한다. 경계면 처리가 까다로운 문제였다.

<소스 코드>

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct dat {
	int x, y, dis;
};

int n, m, p;
char map[1010][1010];
int cnt[1010][1010];
queue <dat> q[10], q2[10];
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };
int ans[10], arr[10];

int main()
{
	int i, j;
	scanf("%d %d %d", &n, &m, &p);
	for (i = 1; i <= p; i++) scanf("%d", &arr[i]);
	for (i = 0; i < n; i++) {
		scanf("%s", map[i]);
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (map[i][j] == '.' || map[i][j] == '#') continue;
			int x = map[i][j] - '0';
			cnt[i][j] = x;
			q[x].push({ i, j, 0 });
		}
	}
	while (1) {
		int ct = 0;
		for (i = 1; i <= p; i++) {
			if (!q[i].empty()) ct = 1;
		}
		if (ct == 0) break;
		for (i = 1; i <= p; i++) {
			while (!q[i].empty()) {
				int n_x = q[i].front().x, n_y = q[i].front().y;
				int ndis = q[i].front().dis;
				q[i].pop();
				for (int k = 0; k < 4; k++) {
					int nx = n_x + dx[k], ny = n_y + dy[k];
					if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
					if (map[nx][ny] == '#' || cnt[nx][ny] > 0) continue;
					if (ndis + 1 >= arr[i]) q2[i].push({ nx, ny, 0 });
					else q[i].push({ nx, ny, ndis + 1 });
					cnt[nx][ny] = i;
				}
			}
			while (!q2[i].empty()) {
				q[i].push(q2[i].front());
				q2[i].pop();
			}
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
//			printf("%d ", cnt[i][j]);
			ans[cnt[i][j]]++;
		}
//		printf("\n");
	}
	for (i = 1; i <= p; i++) printf("%d ", ans[i]);
	return 0;
}

-주유소(13308, 백준)

 다익 + DP문제이다. 생각보다 잘 알려진 유형인것 같다. 처음에 많이 해맸지만 결국 Dijkstra에서 Dp테이블을 채운다는 생각을 해냈다. Dp[i][j] = 1~i번째 도시까지의 경로중 가장 싼 기름가격이 j인 경우의 최소 비용으로 두고 다익스트라를 돌리면 풀린다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

long long n, m;
long long arr[2510];
vector <pair<long long, long long>> vec[2510];
long long dis[2510][2510];

struct dat {
	long long val, idx, cost;
};

bool operator<(const dat& a, const dat& b) {
	return a.val > b.val;
}

void Dijkstra(long long s)
{
	long long i, j;
	priority_queue <dat> pq;
	dis[s][arr[s]] = 0;
	pq.push({ 0, s, arr[s] });
	while (!pq.empty()) {
		long long nidx = pq.top().idx, nval = pq.top().val, ncos = pq.top().cost;
		pq.pop();
		if (dis[nidx][ncos] < nval) continue;
		for (i = 0; i < vec[nidx].size(); i++) {
			long long idx = vec[nidx][i].first, val = nval + vec[nidx][i].second * ncos;
			long long cos = min(ncos, arr[idx]);
			if (dis[idx][cos] > val) {
				dis[idx][cos] = val;
				pq.push({ val, idx, cos });
			}
		}
	}
}

int main()
{
	long long i, j, mx = -2e19;
	scanf("%lld %lld", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &arr[i]);
		if (mx < arr[i]) mx = arr[i];
	}
	for (i = 0; i < m; i++) {
		long long x, y, z;
		scanf("%lld %lld %lld", &x, &y, &z);
		vec[x].push_back({ y, z });
		vec[y].push_back({ x, z });
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= mx; j++) {
			dis[i][j] = 2e19;
		}
	}
	Dijkstra(1);
	long long ans = 2e19;
	for (i = 1; i <= mx; i++) {
		ans = min(ans, dis[n][i]);
	}
	printf("%lld", ans);
	return 0;
}

-구간 곱 구하기(11505, 백준)

 세그먼트 트리 기본 문제이다. 기본적인 덧셈 트리와 달라 어려울 수 있다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

long long n, m, k;
long long arr[1000010];
long long segtree[4000010];

long long init(long long s, long long e, long long node)
{
	if (s == e) return segtree[node] = arr[s];
	long long mid = (s + e) / 2;
	return segtree[node] = (init(s, mid, node * 2) * init(mid + 1, e, node * 2 + 1)) % 1000000007;
}

long long multi(long long s, long long e, long long low, long long high, long long node)
{
	if (e < low || high < s) return 1;
	if (low <= s && e <= high) return segtree[node];
	long long mid = (s + e) / 2;
	return (multi(s, mid, low, high, node * 2) * multi(mid + 1, e, low, high, node * 2 + 1)) % 1000000007;
}

long long edit(long long s, long long e, long long node, long long idx, long long dis) {
	if (idx > e || idx < s) return segtree[node];
	if (s == e) return segtree[node] = dis;
	long long mid = (s + e) / 2;
	return segtree[node] = (edit(s, mid, node * 2, idx, dis) * edit(mid + 1, e, node * 2 + 1, idx, dis)) % 1000000007;
}

int main()
{
	long long i, j;
	scanf("%lld %lld %lld", &n, &m, &k);
	for (i = 1; i <= n; i++) scanf("%lld", &arr[i]);
	init(1, n, 1);
	for (i = 0; i < k + m; i++) {
		long long Q, x, y;
		scanf("%lld %lld %lld", &Q, &x, &y);
		if (Q == 1) {
			edit(1, n, 1, x, y);
			arr[x] = y;
		}
		else {
			long long mx = max(x, y), mn = min(x, y);
			printf("%lld\n", multi(1, n, mn, mx, 1));
		}
	}
	return 0;
}