굳건하게

문제 : https://codeforces.com/contest/1230/problem/C

[알고리즘풀이]

전체 경우의 수가 적기 때문에, BackTracking을 이용해서 문제를 풀 수 있다.

Graph가 주어졌을 때, BackTracking을 이용해 그래프의 노드마다 1 ~ 6 중 번호를 부여하고,

모든 경우의 수에 대해서 Edge 마다 연결된 노드의 번호에 해당하는 주사위를 배정해준다.

N이 많아야 7이므로 모든 경우의 수를 탐색해도 6^7 번만 탐색하면 된다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m, x, y, ans = -1;
int map[8][8];
bool check[7][7];

void bt(vector<int> v);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		map[x][y] = 1, map[y][x] = 1;
	}
	for (int i = 1; i <= 6; i++) {
		vector<int> v;
		v.push_back(i);
		bt(v);
		v.pop_back();
	}
	cout << ans;
	return 0;
}

void bt(vector<int> v) {
	if (v.size() == n) {
		for (int i = 1; i <= 6; i++)
			for (int j = 1; j <= 6; j++)
				check[i][j] = false;
		int c = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] == 1) {
					int A = min(v[i - 1], v[j - 1]);
					int B = max(v[i - 1], v[j - 1]);
					if (check[A][B] == false) {
						check[A][B] = true;
						c++;
					}
				}
			}
		}
		if (c > ans)
			ans = c;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		v.push_back(i);
		bt(v);
		v.pop_back();
	}
}

문제 :  https://codeforces.com/contest/1145/problem/

[알고리즘풀이]

주어진 배열이 오름차순이 아니라면 배열을 반으로 자르는 과정을 반복해서

오름차순인 배열이 나오는 경우를 찾아야한다.

Input이 2의 n승으로 들어오고 값이 최대 16으로 굉장히 작으므로,

배열의 개수가 1, 배열의 크기가 N일 때부터 오름차순인지 아닌지 Check하며

배열의 개수를 2배씩 늘리고, 배열의 크기를 반으로 나누며 모든 경우를 Check한다.

#include<iostream>

using namespace std;

int A[50];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> A[i];

	int size = n, g = 1;
	while (1) {
		for(int i = 0; i < g; i++){
			bool check = false;
			for (int j = 1; j <= size - 1; j++) {
				if (A[size * i+ j] > A[size * i + j + 1]) {
					check = true;
					break;
				}
			}
			if (check == false) {
				cout << size;
				return 0;
			}
		}
		g *= 2;
		size /= 2;
	}
}