2024-04-18

-queuestack(24511, 백준)

 해당 자료형에서 stack에 해당하는 부분은 움직이지 않는다. 즉 queue에 해당하는 부분들의 수만 이용해서 queue를 사용하여, 계산하면 풀린다.

<소스 코드>

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

using namespace std;

int n, m;
int arr[100010];
queue <int> q;
vector <int> vc;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
	for (i = 1; i <= n; i++) {
		int qs;
		scanf("%d", &qs);
		if (arr[i] == 1) continue;
		vc.push_back(qs);
	}
	reverse(vc.begin(), vc.end());
	for (i = 0; i < vc.size(); i++) q.push(vc[i]);
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		q.push(x);
		printf("%d ", q.front());
		q.pop();
	}
	return 0;
}

-캠프 준비(16938, 백준)

 n범위가 15이다. 해당문제를 선택한경우와 안한 경우만 존재하며, 이는 2^15가지의 경우이다. 모든 경우를 탐색한 뒤, 조건을 만족하는 문제의 조합을 찾으면 된다. (순서가 상관없다. -> 조합)

<소스 코드>

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

using namespace std;

int n, l, r, x;
int arr[20];
vector <int> ans;
int ch[20], res;

void dfs(int k, int st)
{
	int i, j;
	if (k >= 2) {
		int sum = 0, mx = -2e9, mn = 2e9;
		for (i = 0; i < ans.size(); i++) {
			//printf("%d ", ans[i]);
			sum += ans[i];
			mx = max(mx, ans[i]);
			mn = min(mn, ans[i]);
		}
		//printf("\n");
		if (l <= sum && sum <= r && mx - mn >= x) res++;
	}
	if (k >= n) return;
	for (i = st; i < n; i++) {
		if (ch[i] == 1) continue;
		ch[i] = 1;
		ans.push_back(arr[i]);
		dfs(k + 1, i + 1);
		ch[i] = 0;
		ans.pop_back();
	}
}

int main()
{
	int i, j;
	scanf("%d %d %d %d", &n, &l, &r, &x);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	dfs(0, 0);
	printf("%d", res);
	return 0;
}

-웜홀(1865, 백준)

 벨만 포드의 기초 응용문제이다. 항상 모든 정점이 연결되어있다는 보장이 없는 문제임으로, 이를 잘 생각해서 풀면 간단한 벨만 포드 알고리즘으로 풀린다.

<소스 코드>

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

using namespace std;

int n, m, w;
int dis[510], ch[510];

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

int main()
{
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		int i, j;
		vector <dat> vec;
		scanf("%d %d %d", &n, &m, &w);
		for (i = 0; i < m; i++) {
			int x, y, z;
			scanf("%d %d %d", &x, &y, &z);
			vec.push_back({ x, y, z });
			vec.push_back({ y, x, z });
		}
		for (i = 0; i < w; i++) {
			int x, y, z;
			scanf("%d %d %d", &x, &y, &z);
			vec.push_back({ x, y, -z });
		}
		for (i = 1; i <= n; i++) dis[i] = 2e9;
		for (i = 1; i <= n; i++) {
			if(dis[i] == 2e9) dis[i] = 0;
			for (j = 0; j < vec.size(); j++) {
				int x = vec[j].x, y = vec[j].y, val = vec[j].val;
				if (dis[x] == 2e9) continue;
				if (dis[y] > dis[x] + val) dis[y] = dis[x] + val;
			}
		}
		int ans = 1;
		for (i = 0; i < vec.size(); i++) {
			int x = vec[i].x, y = vec[i].y, val = vec[i].val;
			if (dis[x] == 2e9) continue;
			if (dis[y] > dis[x] + val) {
				ans = 0;
				break;
			}
		}
		if (ans == 1) printf("NO\n");
		else printf("YES\n");
		vec.clear();
	}
}

-괄호(17623, 백준)

 DP문제이다. 괄호를 숫자로 생각해 숫자의 문자열을 이용한 DP를 생각한다면 쉽게 풀린다. 문자열의 compare함수를 구현하는 것이 까다로웠다.

<소스 코드>

#include <iostream>
#include <algorithm>

using namespace std;

int n, k;
string dp[1010];
char d_s[15] = { ' ', '(', ')', '{', '}', '[', ']'};

string compare(string a, string b)
{
	if (a.size() == 0 || a.size() > b.size()) return b;
	if (b.size() > a.size()) return a;
	return min(a, b);
}

int main()
{
	int t, i, j;
	scanf("%d", &t);
	dp[1] = "12";
	dp[2] = "34";
	dp[3] = "56";
	for (i = 4; i <= 1000; i++) {
		if (i % 2 == 0) dp[i] = compare(dp[i], "1" + dp[i / 2] + "2");
		if (i % 3 == 0) dp[i] = compare(dp[i], "3" + dp[i / 3] + "4");
		if (i % 5 == 0) dp[i] = compare(dp[i], "5" + dp[i / 5] + "6");
		for (j = 1; j < i; j++) dp[i] = compare(dp[i], dp[j] + dp[i - j]);
	}
	while(t--) {
		scanf("%d", &n);
		for (i = 0; i < dp[n].size(); i++) printf("%c", d_s[dp[n][i] - '0']);
		printf("\n");

	}
	return 0;
}