오늘의 문제
14502 연구소
14888 연산자 끼워넣기
14889 스타트와 링크

14502 연구소

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int lab[9][9], tmp[9][9];
vector<pair<int, int>> virus, blank;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int bfs() {
	queue<pair<int, int>> q;
	for (pair<int, int> p : virus) q.push({ p.first, p.second });

	while (!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextx = nowx + dx[i];
			int nexty = nowy + dy[i];

			if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
			if (tmp[nextx][nexty] == 0) {
				tmp[nextx][nexty] = 2;
				q.push({ nextx, nexty });
			}			
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (tmp[i][j] == 0) ++cnt;
		}
	}
	return cnt;
}

int back_tracking() {
	int max_space = 0;
	vector<int> wall(blank.size(), 1);
	wall[0] = 0, wall[1] = 0, wall[2] = 0;

	do {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				tmp[i][j] = lab[i][j];
			}
		}
		for (int i = 0; i < wall.size(); i++) {
			if (wall[i] == 0) {
				tmp[blank[i].first][blank[i].second] = 1;
			}
		}
		int now = bfs();
		max_space = max(max_space, now);
	} while (next_permutation(wall.begin(), wall.end()));

	return max_space;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lab[i][j];
			if (lab[i][j] == 0) blank.emplace_back(make_pair(i, j));
			else if (lab[i][j] == 2) virus.emplace_back(make_pair(i, j));
		}
	}
	cout << back_tracking();
}

미치겠다.. 이 쉬운 문제를 방향 for문에서 i < n으로 오타가 난 걸 못 찾아서 30분을 넘게 헤맸다... 10분도 안 걸려서 풀었으면서😑

14888 연산자 끼워넣기

코드

#include <bits/stdc++.h>
using namespace std;

int n;
long long num[12];
int op[4];
long long min_sum = 10000000000, max_sum = -10000000000;

void operate(long long sum, int k) {
	if (k == n) {
		min_sum = min(min_sum, sum);
		max_sum = max(max_sum, sum);
	}

	for (int i = 0; i < 4; i++) {
		if (op[i] <= 0) continue;
		--op[i];
		if (i == 0) operate(sum + num[k], k + 1);
		else if (i == 1) operate(sum - num[k], k + 1);
		else if (i == 2) operate(sum * num[k], k + 1);
		else operate(sum / num[k], k + 1);
		++op[i];
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> num[i];
	for (int i = 0; i < 4; i++) cin >> op[i];
	operate(num[0], 1);
	cout << max_sum << "\n" << min_sum;
}

재귀(dfs)로 현재까지의 연산 값에 다음 연산을 하도록 했다.

14889 스타트와 링크

코드

#include <bits/stdc++.h>
using namespace std;

int n, min_dif = 10000000;
int ability[21][21];

void team() {
	vector<int> is_start(n, 1);
	fill(is_start.begin(), is_start.begin() + n / 2, 0);

	do {
		vector<int> start, link;
		for (int i = 0; i < n; i++) {
			if (is_start[i]) start.emplace_back(i);
			else link.emplace_back(i);
		}
		int ssum = 0, lsum = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = i + 1; j < n / 2; j++) {
				ssum += ability[start[i]][start[j]];
				ssum += ability[start[j]][start[i]];
				lsum += ability[link[i]][link[j]];
				lsum += ability[link[j]][link[i]];
			}
		}
		min_dif = min(min_dif, abs(ssum - lsum));
	} while (next_permutation(is_start.begin(), is_start.end()));
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> ability[i][j];
		}
	}
	team();
	cout << min_dif;
}

조합을 이용하여 두 팀으로 나누고, 나누어진 두 팀의 능력치를 각각 계산하여 능력치의 차이를 구햇다.