2024-03-17

-백도어(17396, 백준)

 다익 기본문제이다. 시아가 있는곳은 넥서스를 제외하고 모두 제외하고 탐색하면 된다. 범위가 매우 크기때문에 자료형을 주의해야한다.

<소스 코드>

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

using namespace std;

long long n, m;
long long ward[100010];
long long dis[100010];
vector <pair<long long, long long>> vec[100010];

void Dijkstra(long long s)
{
	long long i, j;
	priority_queue <pair<long long, long long>> pq;
	dis[s] = 0;
	pq.push({ 0, s });
	while (!pq.empty()) {
		long long nidx = pq.top().second, nval = -pq.top().first;
		pq.pop();
		if (dis[nidx] < nval) continue;
		for (i = 0; i < vec[nidx].size(); i++) {
			long long idx = vec[nidx][i].first, val = nval + vec[nidx][i].second;
			if (ward[idx] == 0 && dis[idx] > val) {
				dis[idx] = val;
				pq.push({ -val, idx });
			}
		}
	}
}

int main()
{
	long long i, j;
	scanf("%lld %lld", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%lld", &ward[i]);
		dis[i] = 2e15;
	}
	ward[n - 1] = 0;
	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 });
	}
	Dijkstra(0);
	if (dis[n - 1] == 2e15) printf("-1");
	else printf("%lld", dis[n - 1]);
	return 0;
}

-외판원 순회 3(16991, 백준)

 외판원 기초문제이다. 실수형 TSP이다. 탑다운 방으로 풀었다. dp[i][j] = 현재 도시 i이고 현재까지 방문한 도시 리스트가 j일 때 남은 모든 도시를 경유하는데 드는 최소 비용.

<소스 코드>

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

using namespace std;

int n;
double arr[16][16], dp[16][1 << 16];
vector <pair<double, double>> vec;

double TSP(int x, int vis)
{
	int i, j;
	if (vis == (1 << n) - 1) return arr[x][0];
	if (dp[x][vis] != -2e9) return dp[x][vis];
	dp[x][vis] = 2e9;
	for (i = 0; i < n; i++) {
		if (i != x && (vis & (1 << i)) == 0) {
			dp[x][vis] = min(dp[x][vis], TSP(i, vis | (1 << i)) + arr[x][i]);
		}
	}
	return dp[x][vis];
}

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		double x, y;
		scanf("%lf %lf", &x, &y);
		vec.push_back({ x, y });
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (i == j) continue;
			arr[i][j] = sqrt(pow((vec[j].first - vec[i].first), 2) + pow((vec[j].second - vec[i].second), 2));
		}
	}
	for (i = 0; i < 16; i++) {
		for (j = 0; j < (1 << 16); j++) {
			dp[i][j] = -2e9;
		}
	}
	double ans = TSP(0, 0);
	printf("%lf", ans);
	return 0;
}

-보석 모으기(1480, 백준)

 비트필드를 이용한 DP문제이다. 3차원 Dp배열을 잡아 풀었다. 탑다운 방식으로 풀었다. 나중에 바텀업으로도 풀 예정이다. dp[보석 vis][현재 채워진 가방][현재 가방의 사용중인 용량]으로 잡고 보석vis을 비트마스킹을 해 풀었다.

<소스 코드>

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

using namespace std;

int n, m, c;
int arr[15];
int dp[1 << 13][10][20];

int BitDP(int vis, int bag, int cap)
{
	int i, j;
	if (vis == (1 << n) - 1) return 0;
	if (dp[vis][bag][cap] != 0) return dp[vis][bag][cap];
	for (i = 0; i < n; i++) {
		if ((vis & (1 << i)) != 0) continue;
		if (arr[i] > c) continue;
		if (bag + 1 >= m && cap + arr[i] > c) continue;
		if (cap + arr[i] > c) dp[vis][bag][cap] = max(dp[vis][bag][cap], BitDP(vis | (1 << i), bag + 1, arr[i]) + 1);
		else dp[vis][bag][cap] = max(dp[vis][bag][cap], BitDP(vis | (1 << i), bag, cap + arr[i]) + 1);
	}
	return dp[vis][bag][cap];
}

int main()
{
	int i, j;
	scanf("%d %d %d", &n, &m, &c);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	printf("%d", BitDP(0, 0, 0));
	return 0;
}

-그림 교환(1029, 백준)

 비트필드를 이용한 DP문제이다. 마찬가지로 3차원 Dp배열을 잡아 풀었다. 탑다운으로 풀었고, dp[현재 그림을 갖고있는 사람][그림을 살때 지불한 비용][그림을 사고판 사람 vis]으로 풀었다. 그림을 사고판 사람 vis를 비트마스킹하여 풀었다.

<소스 코드>

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

using namespace std;

int n;
int arr[20][20];
int dp[16][10][1 << 16];

int memo(int x, int val, int vis)
{
	int i, j;
	if (dp[x][val][vis] != 0) return dp[x][val][vis];
	for (i = 1; i < n; i++) {
		if (i != x && (vis & (1 << i)) == 0 && arr[x][i] >= val) {
			dp[x][val][vis] = max(dp[x][val][vis], memo(i, arr[x][i], vis | (1 << i)) + 1);
		}
	}
	return dp[x][val][vis];
}

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	printf("%d", memo(0, 0, 0) + 1);
	return 0;
}

-방 배정하기(14697, 백준)

 Dp로 풀었다. n범위가 작아서 블루트포스로도 풀린다고 한다.

>점화식<

if (i >= arr[j]) dp[i] = max(dp[i], dp[i - arr[j]]);

<소스 코드>

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

using namespace std;

int arr[5], dp[310];
int n;

int main()
{
	int i, j;
	scanf("%d %d %d", &arr[0], &arr[1], &arr[2]);
	dp[0] = 1;
	scanf("%d", &n);
	for (i = 0; i <= n; i++) {
		for (j = 0; j < 3; j++) {
			if (i >= arr[j]) dp[i] = max(dp[i], dp[i - arr[j]]);
		}
	}
	printf("%d", dp[n]);
	return 0;
}