2024-02-29

-벽 부수고 이동하기 3(16933, 백준)

 벽부수고이동하기와 같은 로직을 사용한다. dis[i][j][k][t] = 좌표 (i, j) 까지 k번 벽을부수며 갈때 t(밤, 낮구분)시간까지 흐른 시간으로 나타내며, BFS로 그래프 전체를 탐색하며 답을 찾을 수 있다.

<소스코드>

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

using namespace std;

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

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

void BFS(int x, int y)
{
	int i, j;
	queue<dat> q;
	q.push({ x, y, 0, 1 });
	dis[x][y][0][1] = 0;
	while (!q.empty()) {
		int n_x = q.front().x, n_y = q.front().y, nb = q.front().br, nt = q.front().time;
		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 (nt == 1) {
				if (dis[nx][ny][nb][0] > dis[n_x][n_y][nb][nt] + 1 && map[nx][ny] == 0) {
					dis[nx][ny][nb][0] = dis[n_x][n_y][nb][nt] + 1;
					q.push({ nx, ny, nb, 0 });
				}
				if (dis[n_x][n_y][nb][0] > dis[n_x][n_y][nb][nt] + 1) {
					dis[n_x][n_y][nb][0] = dis[n_x][n_y][nb][nt] + 1;
					q.push({ n_x, n_y, nb, 0 });
				}
				if (map[nx][ny] == 1 && nb + 1 <= k && dis[nx][ny][nb + 1][0] > dis[n_x][n_y][nb][nt] + 1) {
					dis[nx][ny][nb + 1][0] = dis[n_x][n_y][nb][nt] + 1;
					q.push({ nx, ny, nb + 1, 0 });
				}
			}
			else {
				if (dis[nx][ny][nb][1] > dis[n_x][n_y][nb][nt] + 1 && map[nx][ny] == 0) {
					dis[nx][ny][nb][1] = dis[n_x][n_y][nb][nt] + 1;
					q.push({ nx, ny, nb, 1 });
				}
				if (dis[n_x][n_y][nb][1] > dis[n_x][n_y][nb][nt] + 1) {
					dis[n_x][n_y][nb][1] = dis[n_x][n_y][nb][nt] + 1;
					q.push({ n_x, n_y, nb, 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][0] = 2e9, dis[i][j][l][1] = 2e9;
		}
	}
	BFS(0, 0);
	int ans = 2e9;
	for (i = 0; i <= k; i++) ans = min(ans, min(dis[n - 1][m - 1][i][0], dis[n - 1][m - 1][i][1]));
	if (ans == 2e9) printf("-1");
	else printf("%d", ans + 1);
	return 0;
}

-가장 긴 증가하는 부분 수열 3(12738, 백준)

 이분 탐색(lower_boind)를 이용하는 LIS기초문제이다. O(nlogn) LIS알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다.

<소스코드>

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

using namespace std;

int main()
{
	int i, j;
	int n;
	scanf("%d", &n);
	vector<int> vec, lis;
	for (i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		vec.push_back(x);
	}
	lis.push_back(vec[0]);
	for (i = 1; i < n; i++) {
		int lb = lower_bound(lis.begin(), lis.end(), vec[i]) - lis.begin();
		int sz = lis.size();
		if (lb >= sz) lis.push_back(vec[i]);
		else lis[lb] = vec[i];
	}
	printf("%d", lis.size());
	return 0;
}

-반도체 설계(2352, 백준)

 마찬가지로, 이분 탐색(lower_boind)를 이용하는 LIS응용문제이다. O(nlogn) LIS알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다. 꼬이지않기 위해서는, 포트의 idx가 증가함에 따라 반대쪽 포트또한 증가해야 함으로, LIS문제로 볼 수 있다.

<소스코드>

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

using namespace std;

int n;
int arr[40010];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	vector <int> lis;
	lis.push_back(arr[0]);
	for (i = 1; i < n; i++) {
		int lb = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
		int sz = lis.size();
		if (lb >= sz) lis.push_back(arr[i]);
		else lis[lb] = arr[i];
	}
	printf("%d", lis.size());
	return 0;
}

-소수가 아닌 수 3(31432, 백준)

 한자리 자연수 N에 11혹은 111같은 수를 곱해 NN(두자리 자연수)꼴로만들면, 소수가 아니게된다.

<소스코드>

#include <stdio.h>

int n;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (x == 0) {
			printf("YES\n0");
			return 0;
		}
		else if (x == 1) {
			printf("YES\n1");
			return 0;
		}
		else {
			printf("YES\n%d", x * 11);
			return 0;
		}
	}
	return 0;
}

-1, 2, 3더하 3(15988, 백준)

 보자마자 DP를 이용한 풀이가 떠올랐다. 1, 2, 3을 갖고 수를 만들어야함으로, 1, 2, 3전의 수들을 만드는 값을 만드는 경우를 모두 더하면, 답이 된다.

>점화식<

Dp[i] = Dp[i-1] + Dp[i-2] + Dp[i-3]

<소스코드>

#include <stdio.h>

int n;
long long dp[1000010];

int main()
{
	int i, j;
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		for (i = 4; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
		printf("%lld\n", dp[n]);
	}
}