브루트 포스 (2)

https://www.acmicpc.net/problem/1107
리모컨

모두 해보면서 안눌러지는 애들 과감하게 버리고
눌러지는 애들 중에 최소를 찾는다

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
bool broken[10];
int go(int channel) {
	if (channel == 0) {
		if (broken[0]) return 0;
		else return 1;
	}
	int len = 0;
	while (channel > 0) {
		if (broken[channel % 10]) return 0;
		len += 1;
		channel /= 10;
	}
	return len;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = abs(n - 100);
	int t;
	cin >> t;
	while (t--) {
		int temp;
		cin >> temp;
		broken[temp] = true;
	}
	for (int i = 0; i < 1000000; i++) {
		int channel = i;
		int length = go(channel);
		if (length > 0) {
			int press = abs(channel - n) + length;
			if (press < ans) ans = press;
		}
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/6064
카잉 달력

2번 씩만 건너뛰어도 모두 돌릴 수 있다 -> x, y 아무 변수로나 시작해도 된다.
주의할 점, 나누어 떨어지는 경우가 문제가 될 수 있다.
최대 값을 찾아야 종료시킬 수 있다. <m:n>년이 마지막 해이다. 이는 m의 배수이자 n의 배수이다.
최대 값을 찾는 것이 헷갈리면 수를 줄여서 해결한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int gcd(int a, int b) {
	if (a % b == 0) return b;
	return gcd(b, a % b);
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;
		int ans = -1;
		int max = (m * n) / gcd(m, n);
		for (int i = x; i <= max; i += m) {
			if ((i - y) % n == 0) {
				ans = i;
				break;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

또는

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int gcd(int a, int b) {
	if (a % b == 0) return b;
	return gcd(b, a % b);
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;
		int ans = -1;
		x -= 1;
		y -= 1;
		int max = (m * n) / gcd(m, n);
		for (int i = x; i <= max; i += m) {
			if (i % n == y) {
				ans = i + 1;
				break;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/1748
수 이어 쓰기 1

#include <iostream>
using namespace std;
int length(int n) {
	int len = 0;
	while (n > 0) {
		len += 1;
		n /= 10;
	}
	return len;
}
int main() {
	int n;
	cin >> n;
	int len = length(n);
	int ten = 1;
	if (len == 1) {
		ten = 0;
	}
	for (int i = 1; i < len; i++) {
		ten = ten * 10;
	}
	int nine = 9;
	long long ans = 0;
	for (int i = 1; i < len; i++) {
		ans += i * nine;
		nine = nine * 10;
	}
	ans += len * (n - ten + 1);
	if (len == 1) ans -= 1;
	cout << ans << '\n';
	return 0;
}

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	long long ans = 0;
	for (int start = 1, len = 1; start <= n; start *= 10, len++) {
		int end = (start * 10 - 1); // 9, 99, 999...
		if (end > n) {
			end = n;
		}
		ans += (long long)(end - start + 1) * len;
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2529
부등호

순열은 순서대로 증거하거나 감소한다. 따라서 조건을 만족하는 경우가 바로
최대 최소이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
char op[10];
int k;
bool go(vector<int>& a) {
	for (int i = 0; i < k; i++) {
		if (op[i] == '<') {
			if (a[i] > a[i + 1]) return false;
		}
		else {
			if (a[i] < a[i + 1]) return false;
		}
	}
	return true;
}
int main() {
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> op[i];
	}
	vector<int> big;
	vector<int> small;
	for (int i = 9; i >= 9 - k; i--) {
		big.push_back(i);
		small.push_back(9 - i);
	}
	do {
		if (go(big)) break;
	} while (prev_permutation(big.begin(), big.end()));
	do {
		if (go(small)) break;
	} while (next_permutation(small.begin(), small.end()));
	for (int i = 0; i < k + 1; i++) {
		cout << big[i];
	}
	cout << '\n';
	for (int i = 0; i < k + 1; i++) {
		cout << small[i];
	}
	cout << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1339
단어 수학

알파벳 대문자를 수로 - 'A'
수를 알파벳 대문자로 + 'A'
수와 알파벳을 매칭 시키는 방법을 잘 기억해야 한다. 알파벳의 수 만큼 배열을 판다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<string> word;
vector<int> num;
vector<char> cha;
int alpha[26];
int n;
int go() {
	int result = 0;
	for (int i = 0; i < num.size(); i++) {
		alpha[cha[i] - 'A'] = num[i];
	}
	for (int i = 0; i < n; i++) {
		int prev_result = 0;
		for (int j = 0; j < word[i].size(); j++) {
			prev_result =
				prev_result * 10 + alpha[word[i][j] - 'A'];
		}
		result += prev_result;
	}
	return result;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	string temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		word.push_back(temp);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < word[i].size(); j++) {
			alpha[word[i][j] - 'A'] = 1;
		}
	}
	int start = 9;
	for (int i = 0; i < 26; i++) {
		if (alpha[i]) {
			cha.push_back(i + 'A');
			num.push_back(start);
			start -= 1;
		}
	}
	int ans = 0;
	do {
		int temp;
		temp = go();
		if (ans < temp) ans = temp;
	} while (prev_permutation(num.begin(), num.end()));
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/14889
스타트와 링크

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<vector<int>> s(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> s[i][j];
		}
	}
	vector<int> combi(n);
	for (int i = 0; i < n; i++) {
		if (i < n / 2) combi[i] = 0;
		else combi[i] = 1;
	}
	int ans = 2000000;
	do {
		int t1 = 0;
		int t2 = 0;
		vector<int> team1;
		vector<int> team2;
		for (int i = 0; i < n; i++) {
			if (combi[i] == 0) {
				team1.push_back(i);
			}
			else {
				team2.push_back(i);
			}
		}
		for (int i = 0; i < n / 2 ; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j)continue;
				t1 += s[team1[i]][team1[j]];
				t2 += s[team2[i]][team2[j]];
			}
		}
		int diff = abs(t1 - t2);
		if (diff < ans) ans = diff;
	} while (next_permutation(combi.begin(), combi.end()));
	cout << ans << '\n';
	return 0;
}

백트래킹
재귀 함수를 이용해 더 이상 함수 호출이 의미 없는 경우 리턴한다.
던질까 말까

재귀 함수의 기본 - 정답을 찾은 경우, 다음 경우, 그리고 종료 조건

https://www.acmicpc.net/problem/14889
스타트와 링크

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 2000
int n;
int s[20][20];
int go(int index, vector<int>& team1, vector<int>& team2) {
	if (team1.size() > n / 2) return MAX;
	if (team2.size() > n / 2) return MAX;
	if (index == n) {
		int t1 = 0;
		int t2 = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				t1 += s[team1[i]][team1[j]];
				t2 += s[team2[i]][team2[j]];
			}
		}
		int diff = abs(t1 - t2);
		return diff;
	}
	int ans = MAX;
	
	team1.push_back(index);
	int temp1 = go(index + 1, team1, team2);
	team1.pop_back();
	if (temp1 < ans) ans = temp1;

	team2.push_back(index);
	int temp2 = go(index + 1, team1, team2);
	team2.pop_back();
	if (temp2 < ans) ans = temp2;
	return ans;
}
int main() {
	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 >> s[i][j];
		}
	}
	vector<int> team1, team2;
	cout << go(0, team1, team2) << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2529
부등호

숫자로 구성된 문자열은 앞에 0이 포함되건 말건 그냥 대소 비교가 가능하다.
문자열에서 문자를 하나 떼서 비교할수도 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int k;
bool check[10];
vector<string> ans;
char op[10];
bool possi(char op, char num1, char num2) {
	if (op == '<') {
		if (num1 > num2) return false;
	}
	else {
		if (num1 < num2) return false;
	}
	return true;
}
void go(int index, string num) {
	if (index == k + 1) {
		ans.push_back(num);
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (check[i]) continue;
		if (index == 0 || possi(op[index - 1], num[index - 1],
			i + '0')) {
			check[i] = true;
			go(index + 1, num + to_string(i));
			check[i] = false;
		}
	}
}
int main() {
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> op[i];
	}
	go(0, "");
	auto p = minmax_element(ans.begin(), ans.end());
	cout << *p.second << '\n';
	cout << *p.first << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1248
맞춰봐

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
char s[20][20];
vector<int> num;
int n;
bool suc;
bool possi(int index) {
	int sum = 0;
	for (int i = index; i >= 0; i--) {
		sum += num[i];
		if (s[i][index] == '+') {
			if (sum <= 0) return false;
		}
		else if (s[i][index] == '-') {
			if (sum >= 0) return false;
		}
		else {
			if (sum != 0) return false;
		}
	}
	return true;
}
void go(int index) {
	if (suc) return;
	if (index == n) {
		for (int i = 0; i < n; i++) {
			cout << num[i] << ' ';
		}
		suc = true;
		cout << '\n';
		return;
	}
	for (int i = -10; i <= 10; i++) {
		num.push_back(i);
		if (possi(index)) {
			go(index + 1);
		}
		num.pop_back();
	}
	return;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			cin >> s[i][j];
		}
	}
	go(0);
	return 0;
}

https://www.acmicpc.net/problem/9663
N-Queen

마이너스 배열은 없어 같은 기준만큼 더해주면 됨

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
bool col[15];
bool rd[30];
bool ld[100];
int n;
int ans = 0;
void go(int index) {
	if (index == n) {
		ans += 1;
		return;
	}
	for (int i = 0; i < n; i++) {
			if (rd[index + i] || col[i] || ld[i-index + n]) continue;
			col[i] = true;
			rd[i + index] = true;
			ld[i - index + n] = true;
			go(index + 1);
			col[i] = false;
			rd[i + index] = false;
			ld[i-index + n] = false;
	}
}
int main() {
	cin >> n;
	go(0);
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2580
스도쿠 나눗셈과 퍼센트 연산 비교 잘하자 헷갈리지 말고

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool row[9][10];
bool col[9][10];
bool sq[9][10];
int s[9][9];
int n = 9;
vector<pair<int, int>> blank;
bool suc;
void go(int index) {
	if (suc) return;
	if (index == blank.size()) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << s[i][j] << ' ';
			}
			cout << '\n';
		}
		cout << '\n';
		suc = true;
		return;
	}
	int i = blank[index].first;
	int j = blank[index].second;
	int sq_val = ((i / 3) * 3) + (j / 3);
	for (int k = 1; k <= 9; k++) {
		if (row[i][k] || col[j][k] ||sq[sq_val][k]) continue;
		row[i][k] = true;
		col[j][k] = true;
		sq[sq_val][k] = true;
		s[i][j] = k;
		go(index + 1);
		row[i][k] = false;
		col[j][k] = false;
		sq[sq_val][k] = false;
		s[i][j] = 0;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> s[i][j];
			if (s[i][j] == 0) {
				blank.push_back(make_pair(i, j));
			}
			else {
				row[i][s[i][j]] = true;
				col[j][s[i][j]] = true;
				int sq_val = ((i / 3) * 3) + (j / 3);
				sq[sq_val][s[i][j]] = true;
			}
		}
	}
	go(0);
	return 0;
}

https://www.acmicpc.net/problem/1987
알파벳

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
char s[21][21];
int r, c;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans = 0;
bool check_alp[26];
void go(int x, int y, int cnt) {
	if (x == 1 && y == 1) {
		check_alp[s[x][y] - 'A'] = true;
	}
	for(int i=0; i<4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx <= 0 || nx > r || ny <= 0 || ny > c) continue;
		if (check_alp[s[nx][ny] - 'A']) continue;
		check_alp[s[nx][ny] - 'A'] = true;
		go(nx, ny, cnt + 1);
		check_alp[s[nx][ny] - 'A'] = false;
	}
	if (ans < cnt) ans = cnt;
}
int main(){
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> s[i][j];
		}
	}
	go(1, 1, 1);
	cout << ans << '\n';
	return 0;
}

비트마스크

https://www.acmicpc.net/problem/14889
스타트와 링크

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> s[i][j];
		}
	}
	int ans = -1;
	for (int i = 0; i < (1 << n); i++) {
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) cnt += 1; // 1의 개수
		}
		if (cnt != n / 2) continue;
		vector<int> team1, team2;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) team1.push_back(j);
			else team2.push_back(j);
		}
		int t1 = 0;
		int t2 = 0;
		for (int k1 = 0; k1 < n / 2; k1++) {
			for (int k2 = 0; k2 < n / 2; k2++) {
				if (k1 == k2) continue;
				t1 += s[team1[k1]][team1[k2]];
				t2 += s[team2[k1]][team2[k2]];
			}
		}
		int diff = t1 - t2;
		if (diff < 0) diff = -diff;
		if (ans == -1 || diff < ans) {
			ans = diff;
		}
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/14391
종이 조각

각각의 칸은 가로 또는 세로에 속한다.
더하는 것도 가로 따로 세로 따로 더하는 것이 더 편할수도

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, m;
int a[4][4];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &a[i][j]);
		}
	}
	int ans = 0;
	for (int s = 0; s < (1 << (n * m)); s++) {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int temp = 0;
			for (int j = 0; j < m; j++) {
				int k = i * m + j;
				if ((s & (1 << k)) == 0) {
					temp = temp * 10 + a[i][j];
				}
				else {
					sum += temp;
					temp = 0;
				}
			}
			sum += temp;
		}
        // 단순히 진행 순서만 변경하면 됨
		for (int j = 0; j < m; j++) {
			int temp = 0;
			for (int i = 0; i < n; i++) {
				int k = i * m + j;
				if ((s & (1 << k)) == (1 << k)) {
					temp = temp * 10 + a[i][j];
				}
				else {
					sum += temp;
					temp = 0;
				}
			}
			sum += temp;
		}
		if (ans < sum) ans = sum;
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1062
가르침

단어를 모두 끌고 다닐 필요가 없다. 단어 -> 비트마스크
비트 마스크를 만들어서 비교한다. for문으로 했을 때, 마스크의 1의 개수를 세기가 힘들다.

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> words;
int ans = 0;
void count(int mask) {
	int cnt = 0;
	for (int word : words) {
		if ((mask & word) == word) {
			cnt += 1;
		}
	}
	if (ans < cnt) ans = cnt;
}
void go(int index, int k, int mask) {
	if (k < 0) return;
	if (index == 26) {
		if (k == 0) count(mask);
		return;
	}
	go(index + 1, k - 1, mask | (1 << index));
	if (index != 'a' - 'a' && index != 'n' - 'a' &&
		index != 't' - 'a' && index != 'c' - 'a' && index != 'i' - 'a') {
		go(index + 1, k, mask);
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	if (k < 5) {
		cout << 0 << '\n';
		return 0;
	}
	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		int mask = 0;
		for (char x : temp) {
			mask |= (1 << (x - 'a'));
		}
		words.push_back(mask);
	}
	go(0, k, 0);
	cout << ans << '\n';
	return 0;
}

for문 쓰는 경우 108ms, 위의 경우는 24ms

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> words;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	if (k < 5) {
		cout << 0 << '\n';
		return 0;
	}
	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		int mask = 0;
		for (char x : temp) {
			mask |= (1 << (x - 'a'));
		}
		words.push_back(mask);
	}
	int checking = (1 << ('a' - 'a')) | (1 << ('c' - 'a')) |
		(1 << ('i' - 'a')) | (1 << ('n' - 'a') | (1 << ('t' - 'a')));
	int ans = 0;
	for (int i = 0; i < (1 << 26); i++) {
		int cnt = 0;
		if ((i & checking) != checking) continue;
		for (int j = 0; j < 26; j++) {
			if (i & (1 << j)) {
				cnt += 1;
			}
		}
		if (cnt != k) continue;
		int temp = 0;
		for (int word : words) {
			if ((i & word) == word) temp += 1;
		}
		if (ans < temp) ans = temp;
	}
	cout << ans << '\n';
	return 0;
}