굳건하게

문제 : https://www.acmicpc.net/problem/14889

[알고리즘풀이]

백트레킹 기법을 이용하여, ( N / 2 ) 명을 뽑는 모든 경우의 수에 대해 Team 능력치를 구하고, 차이를 계산한다.

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

using namespace std;

int m = 1000000000, n;
int map[20][20];

void bt(int, int, vector<int>);

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

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	vector<int> v;
	for (int i = 0; i < n / 2; i++) {
		v.push_back(i);
		bt(1, i, v);
		v.pop_back();
	}
	cout << m;
}

void bt(int k, int l, vector<int> v) {
	if (k == n / 2) {
		int t1 = 0, t2 = 0;
		bool c[20] = {};
		for (int i = 0; i < v.size(); i++)
			c[v[i]] = true;
		vector<int> v2;
		for (int i = 0; i < n; i++)
			if (c[i] == false)
				v2.push_back(i);
		
		for (int i = 0; i < v.size(); i++)
			for (int j = 0; j < v.size(); j++)
					t1 += map[v[i]][v[j]];

		for (int i = 0; i < v2.size(); i++)
			for (int j = 0; j < v2.size(); j++)
					t2 += map[v2[i]][v2[j]];
		if (abs(t1 - t2) < m)
			m = abs(t1 - t2);
		return;
	}

	for (int i = l + 1; i < n; i++) {
		v.push_back(i);
		bt(k + 1, i, v);
		v.pop_back();
	}
	return;
}

문제 : https://www.acmicpc.net/problem/14888

[알고리즘풀이]

백트레킹 기법을 이용하여, 가능한 모든 경우에 대해서 수식을 만들어 계산을 해본다.

( 0 : + , 1 : - , 2 : * , 3 : / 를 의미 )

#include<iostream>
#include<vector>

using namespace std;

int ma = -1000000001, mi = 1000000001;

void bt(int, vector<int>, vector<int>, vector<int>);

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

	int n;
	cin >> n;
	vector<int> v(n), o(4), k;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	for (int i = 0; i < 4; i++)
		cin >> o[i];
	bt(0, v, o, k);
	cout << ma << '\n' << mi;
}

void bt(int n, vector<int> v, vector<int> o, vector<int> k) {
	if (n == v.size() - 1) {
		int temp = v[0];
		for (int i = 0; i < k.size(); i++) {
			if (k[i] == 0) {
				temp += v[i + 1];
			}
			else if (k[i] == 1) {
				temp -= v[i + 1];
			}
			else if (k[i] == 2) {
				temp *= v[i + 1];
			}
			else {
				temp /= v[i + 1];
			}
		}
		if (temp < mi)
			mi= temp;
		if (temp > ma)
			ma = temp;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (o[i] != 0) {
			o[i]--;
			k.push_back(i);
			bt(n + 1, v, o, k);
			k.pop_back();
			o[i]++;
		}
	}
	return;
}

문제 : https://www.acmicpc.net/problem/2580

[알고리즘풀이]

1. 빈 칸을 모두 저장한다.

2. 빈 칸을 순회하며, 빈 칸에 들어갈 수 있는 모든 수들을 Check하고, 그 수를 넣으며 백트레킹을 실행한다.

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

using namespace std;

int map[9][9];
bool flag;

void bt(int, vector<int>, vector<int>);

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

	vector<int> x, y;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++){
			cin >> map[i][j];
			if (map[i][j] == 0) {
				x.push_back(i);
				y.push_back(j);
			}
		}
	bt(0, x, y);
}

void bt(int n, vector<int> x, vector<int> y) {
	if (flag)
		return;

	if (n == x.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << map[i][j] << ' ';
			cout << '\n';
		}
		flag = true;
		return;
	}
	vector<int> v; // 넣을 수 있는 수를 저장한다.
	int x_c = (x[n] / 3) * 3, y_c = (y[n] / 3) * 3;
	bool check[10] = {};
	// 행부터
	for (int i = 0; i < 9; i++)
		check[map[x[n]][i]] = true;
	// 열도
	for (int i = 0; i < 9; i++)
		check[map[i][y[n]]] = true;
	for (int i = x_c; i < x_c + 3; i++)
		for (int j = y_c; j < y_c + 3; j++)
			check[map[i][j]] = true;
	for (int i = 1; i <= 9; i++)
		if (check[i] == false)
			v.push_back(i);
	for (int i = 0; i < v.size(); i++) {
		map[x[n]][y[n]] = v[i];
		bt(n + 1, x, y);
		map[x[n]][y[n]] = 0;
	}
	return;
}

문제 : https://www.acmicpc.net/problem/2981

[수학지식]

수학적인 지식이 정말 많이 쓰인 문제입니다.

차근차근 정리해보도록 하겠습니다.

K개의 자연수가 있다고 하자. ( 1 ≤ k ≤ 100 )

이때, M으로 나눈 나머지가 t로 모두 같다고 하면 다음과 같은 식이 성립한다.

[정리1]

이 식을 이용해 다음과 같은 정리를 얻을 수 있습니다.

[정리2]

임의의 i, j 에 대해

[정리3]

즉, 두 개의 숫자의 차이는 M으로 나눠짐을 알 수 있습니다.

[최종정리]

M으로 모든 숫자들을 나누었을 때, 나머지가 같다면 정리 2,3에 의해 M은 임의의 두 수의 차이의 약수가 됩니다.

즉, M은 두 숫자의 차이 값들의 공약수가 됩니다.

따라서, 모든 숫자들의 차이에 대해서 최대공약수를 구하고,  최대공약수의 약수를 출력해주면 되는 문제입니다.

[+추가정리]

수학과 정수론 시간에 배우는 정리로, 증명은 너무 간단하니 생략하겠습니다.

위의 정리를 이용하면 다음과 같은 연산 낭비를 막을 수 있습니다.

예를 들어 N1, N2, N3, N4 ( N1 < N2 < N3 < N4 ) 수가 주어졌을 때, 가능한 모든 차이는

N4 - N3 / N4 - N2 / N4 - N1 / N3 - N2 / N3 - N1 / N2 - N1 이 됩니다.

그리고 우리는 이 6개의 값에 대해서 GCD(최대공약수)를 구해야 됩니다.

하지만 위의 정리를 이용하면, 

N4 - N3 / N3 - N2 / N2 - N1 의 최대공약수만 구해도 됩니다.

[알고리즘풀이]

1. 입력된 숫자들을 크기에 따라 정렬해준다.

2. 입력된 숫자들의 모든 차이에 대해서 최대 공약수(g)를 구해준다.

3. 그 최대공약수의 약수(g)들을 출력해준다.

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

using namespace std;

int gcd(int a, int b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

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

	int n;
	cin >> n;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());

	int g = gcd(v[1] - v[0], v[1] - v[0]);

	for (int i = 1; i < n - 1; i++) {
		g = gcd(g, v[i + 1] - v[i]);
	}
	vector<int> vv;

	for (int i = 1; i * i <= g; i++) {
		if (g % i == 0) {
			if (i == 1) vv.push_back(g);
			else if (i * i == g)
				vv.push_back(i);
			else{
				vv.push_back(i);
				vv.push_back(g / i);
			}
		}
	}

	sort(vv.begin(),vv.end());
	for (int i = 0; i < vv.size(); i++)
		cout << vv[i] << ' ';
}