2024-02-28

-분수의 합(1735, 백준)

두 분수를 입력받아 두 분수의 합을 기약분수의 형태로 나타내는 문제이다. 우선, 두분수를 통분시킨후, 만들어진 분수의 분자, 분모를 가지고 GCD를 돌리면 되는 간단한 문제이다.(기약분수 -> 서로소 = GCD 가 1인경우)

<소스코드>

#include <stdio.h>

int a, b;
int c, d;

int GCD(int x, int y)
{
	if (y == 0) return x;
	else return GCD(y, x % y);
}

int main()
{
	int i, j;
	scanf("%d %d", &a, &b);
	scanf("%d %d", &c, &d);
	int x = (a * d) + (c * b);
	int y = d * b;
	while (1)
	{
		int gc;
		if (x > y) gc = GCD(x, y);
		else gc = GCD(y, x);
		if (gc == 1) break;
		x /= gc;
		y /= gc;
	}
	printf("%d %d", x, y);
	return 0;
}

-소수&팰린드롬(1747, 백준)

N보다 크거나 같고, 소수인 팰린드롬(뒤집어도 같은수)를 구하는 문제이다. 에라토스테네스의 체 + 팰린드롬문제이다. 에라토스테네스의 체로 n보다큰 소수를 검사해가며 팰린드롬이라면 출력하면 된다.

<소스코드>

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

using namespace std;

int prime[1100010];
vector <int> vec;
int n;

void IsPrime()
{
	int i, j;
	prime[2] = 1;
	for (i = 3; i <= 1100000; i++) {
		if (i % 2 == 0 || prime[i] == 1) continue;
		for (j = i * 2; j <= 1100000; j += i) {
			prime[j] = 1;
		}
	}
	if(n <= 2) vec.push_back(2);
	for (i = 3; i <= 1100000; i++) if (i >= n && i % 2 != 0 && prime[i] == 0) vec.push_back(i);
	return;
}

int main()
{
	int i, j;
	scanf("%d", &n);
	IsPrime();
	for (i = 0; i < vec.size(); i++) {
		vector <int> pel;
		int x = vec[i];
		while (x >= 1) {
			pel.push_back(x % 10);
			x /= 10;
		}
		int siz = pel.size();
		int ch = 0;
		for (j = 0; j < siz / 2; j++) {
			if (pel[j] != pel[siz - j - 1]) ch = 1;
		}
		if (ch == 0) {
			printf("%d", vec[i]);
			break;
		}
	}
	return 0;
}

-벽 부수고 이동하기 2(14442, 백준)

3차원 배열을 이용해 방문처리를 해주면된다. dis[i][j][k] => 1, 1에서 i, j까지 k번 벽을 부수며 갔을때 걸리는 최소 경로.

<소스코드>

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

using namespace std;

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

int n, m, k;
int map[1010][1010];
int dis[1010][1010][15];
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };

void BFS(int x, int y)
{
	int i;
	queue <dat> q;
	q.push({ x, y, 0 });
	dis[x][y][0] = 0;
	while (!q.empty()) {
		int n_x = q.front().x, n_y = q.front().y, n_br = q.front().br;
		q.pop();
		for (i = 0; i < 4; i++) {
			int nx = n_x + dx[i], ny = n_y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (map[nx][ny] == 0 && dis[nx][ny][n_br] > dis[n_x][n_y][n_br] + 1) {
				dis[nx][ny][n_br] = dis[n_x][n_y][n_br] + 1;
				q.push({ nx, ny, n_br });
			}
			if (n_br + 1 <= k) {
				if (map[nx][ny] == 1 && dis[nx][ny][n_br + 1] > dis[n_x][n_y][n_br] + 1) {
					dis[nx][ny][n_br + 1] = dis[n_x][n_y][n_br] + 1;
					q.push({ nx, ny, n_br + 1 });
				}
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d %d", &n, &m, &k);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%1d", &map[i][j]);
			for (int l = 0; l <= k; l++) dis[i][j][l] = 2e9;
		}
	}
	BFS(0, 0);
	int ans = 2e9;
	for (i = 0; i <= k; i++) ans = min(ans, dis[n - 1][m - 1][i]);
	if (ans == 2e9) printf("-1");
	else printf("%d", ans + 1);
	return 0;
}

-말이 되고픈 원숭이(1600, 백준)

마찬가지로 3차원 배열을 이용해 방문처리를 해주면된다. dis[i][j][k] => 1, 1에서 i, j까지 k번 말처럼 이동하여 갔을때 걸리는 최소 경로.

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

using namespace std;

int n, m, k;
int dis[210][210][35];
int map[210][210];
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };
int kx[10] = { 2, 2, 1, 1, -1 ,-1, -2, -2 };
int ky[10] = { 1, -1, 2, -2, 2, -2, 1, -1 };

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

void BFS(int x, int y)
{
	int i;
	queue<dat> q;
	q.push({ x, y, 0 });
	dis[x][y][0] = 0;
	while (!q.empty()) {
		int n_x = q.front().x, n_y = q.front().y, n_jump = q.front().jump;
		q.pop();
		for (i = 0; i < 4; i++) {
			int nx = n_x + dx[i], ny = n_y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (map[nx][ny] == 0 && dis[nx][ny][n_jump] > dis[n_x][n_y][n_jump] + 1) {
				dis[nx][ny][n_jump] = dis[n_x][n_y][n_jump] + 1;
				q.push({ nx, ny, n_jump });
			}
		}
		if (n_jump + 1 <= k) {
			for (i = 0; i < 8; i++) {
				int nx = n_x + kx[i], ny = n_y + ky[i];
				if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				if (map[nx][ny] == 0 && dis[nx][ny][n_jump + 1] > dis[n_x][n_y][n_jump] + 1) {
					dis[nx][ny][n_jump + 1] = dis[n_x][n_y][n_jump] + 1;
					q.push({ nx, ny, n_jump + 1 });
				}
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d %d", &k, &m, &n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			for (int l = 0; l <= k; l++) dis[i][j][l] = 2e9;
		}
	}
	BFS(0, 0);
	int ans = 2e9;
	for (i = 0; i <= k; i++) ans = min(ans, dis[n - 1][m - 1][i]);
	if (ans == 2e9) printf("-1");
	else printf("%d", ans);
	return 0;
}

-백조의 호수(3197, 백준)

  BFS 심화문제이다. 처음부터 빙판을 녹이며 탐색했다간 시간초과가 나오게됨으로, 다음과같은 두 조건을 찾은 뒤 탐색해 주어야한다.

1. 빙판을 녹일땐, 바로 전날 녹았던 빙판에서 시작하면된다.(queue에 담아서 처리)

2. 백조를 탐색할때 만난 빙판은 다음날 녹게됨으로, 미리 queue에 담아두었다가 다음날 처리하면 된다.

이렇게 BFS를 돌리면 O(C*R)안에 풀린다. 한참해맸던 문제이다.

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

using namespace std;

int R, C;
char s[1510][1510];
int ch[1510][1510], ch2[1510][1510];
queue <pair<int, int>> q, q1, q2, q3;
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };

int main()
{
	int i, j;
	scanf("%d %d", &R, &C);
	for (i = 0; i < R; i++) scanf("%s", s[i]);
	int sx, sy;
	for (i = 0; i < R; i++) {
		for (j = 0; j < C; j++) {
			if (s[i][j] == 'L') sx = i, sy = j;
			if (s[i][j] != 'X') q.push({ i, j });
		}
	}
	int day = 0;
	q2.push({ sx, sy });
	ch2[sx][sy] = 1;
	while (1)
	{
		while (!q.empty()) {
			int n_x = q.front().first, n_y = q.front().second;
            ch[n_x][n_y] = 1;
			q.pop();
			for (i = 0; i < 4; i++) {
				int nx = n_x + dx[i], ny = n_y + dy[i];
				if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
				if (ch[nx][ny] == 1) continue;
				if(s[nx][ny] == 'X') q1.push({nx, ny});
			    ch[nx][ny] = 1;
			}
		}
		while (!q1.empty()) {
			int nx = q1.front().first, ny = q1.front().second;
			q1.pop();
			s[nx][ny] = '.';
			q.push({ nx, ny });
		}
		day++;
		while (!q2.empty()) {
			int n_x = q2.front().first, n_y = q2.front().second;
			q2.pop();
			for (i = 0; i < 4; i++) {
				int nx = n_x + dx[i], ny = n_y + dy[i];
				if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
				if (ch2[nx][ny] == 1) continue;
				ch2[nx][ny] = 1;
				if (s[nx][ny] == 'X') {
					q3.push({ nx, ny });
					continue;
				}
				if (s[nx][ny] == 'L') {
					printf("%d", day);
					return 0;
				}
				q2.push({ nx, ny });
			}
		}
		while (!q3.empty()) {
			q2.push(q3.front());
			q3.pop();
		}
	}
	return 0;
}