.jpg)
Brute Force
모든 경우의 수를 다 해보는 것을 브루트 포스라 한다.
- 문제의 가능한 경우를 계산해 O(1억)이 넘지 않는지 확인한다.
- 1에서 문제가 없는 경우, 가능한 모든 방법을 모두 해 본다.
- 이때 하나의 경우라도 빠짐이 없이 해야 한다.
- for, 순열, 재귀, Bit-mask를 이용한다.
- 답을 구한다.
https://www.acmicpc.net/problem/2309
일곱 난쟁이
#include <iostream>
#include <algorithm>
using namespace std;
int a[9];
int n = 9;
int main() {
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
sort(a, a + 9);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (sum - a[i] - a[j] == 100) {
for (int k = 0; k < n; k++) {
if (k == i || k == j) continue;
cout << a[k] << '\n';
}
return 0; //단 한번의 실행
}
}
}
return 0;
}https://www.acmicpc.net/problem/1476
날짜 계산
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int e, s, m;
cin >> e >> s >> m;
for (int i = 0;; i++) {
int x = i * 28 + s;
if ((x - e) % 15 == 0 && (x - m) % 19 == 0) {
cout << x << '\n';
return 0;
}
}
return 0;
}#include <iostream>
using namespace std;
int main(){
int E, S, M;
cin >> E >> S >> M;
int e = 1, s = 1, m = 1;
for(int i = 1;; i++){
if(e == E && s == S && m == M){
cout << i << '\n';
return 0;
}
e +=1; s += 1; m +=1;
if(e == 16) e = 1;
if(s == 29) s = 1;
if(m == 20) m = 1;
}
return 0;
}https://www.acmicpc.net/problem/14500
테트로미노
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main() {
int n, m;
scanf("%d %d", &n, &m);
int a[500][500];
memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &a[i][j]);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//1
if (j + 3 < m) {
int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i][j + 3];
if (ans < temp) ans = temp;
}
if (i + 3 < n) {
int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 3][j];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j + 1 < m) {
int temp = a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j + 2 < m) {
int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 1][j + 2];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j - 2 >= 0) {
int temp = a[i][j] + a[i + 1][j] + a[i + 1][j - 1] + a[i + 1][j - 2];
if (ans < temp) ans = temp;
}
if (i + 2 < n && j + 1 < m) {
int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 2][j + 1];
if (ans < temp) ans = temp;
}
if (i + 2 < n && j - 1 >= 0) {
int temp = a[i][j] + a[i][j - 1] + a[i + 1][j - 1] + a[i + 2][j - 1];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j + 2 < m) {
int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j + 2];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j - 2 >= 0) {
int temp = a[i][j] + a[i][j - 1] + a[i][j - 2] + a[i + 1][j - 2];
if (ans < temp) ans = temp;
}
if (i + 2 < n && j + 1 < m) {
int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j + 1];
if (ans < temp) ans = temp;
}
if (i + 2 < n && j - 1 >= 0) {
int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j - 1];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j + 2 < m) {
int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i][j + 2];
if (ans < temp) ans = temp;
}
if (i -1 >=0 && j + 2 <m) {
int temp = a[i][j] + a[i][j + 1] + a[i - 1][j + 1] + a[i][j + 2];
if (ans < temp) ans = temp;
}
if (i + 1 < n && i - 1 >= 0 && j - 1 >= 0) {
int temp = a[i][j] + a[i][j - 1] + a[i + 1][j - 1] + a[i - 1][j - 1];
if (ans < temp) ans = temp;
}
if (i + 1 < n && i - 1 >= 0 && j + 1 < m) {
int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i - 1][j + 1];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j + 2 < m) {
int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j + 2];
if (ans < temp) ans = temp;
}
if (i + 1 < n && j - 2 >= 0) {
int temp = a[i][j] + a[i][j - 1] + a[i + 1][j - 1] + a[i + 1][j - 2];
if (ans < temp) ans = temp;
}
if (i + 2 < n && j + 1 < m) {
int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 2][j + 1];
if (ans < temp) ans = temp;
}
if (i + 2 < n && j - 1 >= 0) {
int temp = a[i][j] + a[i + 1][j] + a[i + 1][j - 1] + a[i + 2][j - 1];
if (ans < temp) ans = temp;
}
}
}
printf("%d\n", ans);
return 0;
}#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {
{{0,1}, {0,2}, {0,3}},
{{1,0}, {2,0}, {3,0}},
{{0,1}, {1,0}, {1,1}},
{{-1,0}, {-1, 1}, {-1,2}},
{{1,0}, {1,1}, {1,2}},
{{0,1}, {1,1}, {2,1}},
{{-2,1}, {-1, 1}, {0,1}},
{{1,0}, {1, -1}, {1, -2}},
{{-1,0}, {-1, -1}, {-1, -2}},
{{0, -1}, {1, -1}, {2,-1}},
{{0,-1}, {-1, -1}, {-2, -1}},
{{0,-1}, {1, -1}, {1, -2}},
{{1,0}, {1,1}, {2,1}},
{{0,1}, {1, 1}, {1,2}},
{{1,0}, {1,-1}, {2,-1}},
{{1,0}, {1,1}, {2,0}},
{{0,-1}, {1,-1}, {0,-2}},
{{0,-1}, {-1, -1}, {0, -2}},
{{1,0}, {1,-1}, {2,0}}
};
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 19; k++) {
bool ok = true;
int sum = a[i][j];
for (int l = 0; l < 3; l++) {
int x = j + block[k][l][0];
int y = i + block[k][l][1];
if (0 <= y && y < n && 0 <= x && x < m) {
sum += a[y][x];
}
else {
ok = false;
break;
}
}
if (ok && ans < sum) {
ans = sum;
}
}
}
}
cout << ans << endl;
return 0;
}대칭은 그림을 말그대로 대칭 시켜보면 된다.
순열
크기가 N인 수열은 N!개가 존재한다.
사전 순으로 다음에 오는 순열은 next_permutation, 이전 순열은 prev_permutation을 사용한다.
함수를 사용하지 않고 직접 다음 순열을 찾는 방법(이전 순열의 경우 부등호만 반대로)
(1) A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾아야 한다.
(2) j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
(3) A[i-1]과 A[j]를 swap 한다.
(4) A[i] 부터 순열을 뒤집는다.
bool next_permutation(int *a, int n){
// 감소 수열 찾기
int i = n-1;
while(i > 0 && a[i-1] >= a[i]) i -=1;
if(i <=0) return false;
int j = n-1;
// 뒤집기 시작
while(a[j] <= a[i-1]) j -= 1;
// 없는 경우 swap(a[i-1] , a[i-1])
swap(a[i-1], a[j]);
j = n-1;
while(i < j){
swap(a[i], a[j]);
i += 1; j -= 1;
}
return true;
}https://www.acmicpc.net/problem/10972
다음 순열
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool next_permutation(int n, vector<int>& a) {
int index = n - 1;
while (index > 0 && a[index - 1] >= a[index]) index -= 1;
if (index == 0) return false;
int j = n - 1;
while (a[j] <= a[index - 1]) j -= 1;
swap(a[index - 1], a[j]);
j = n - 1;
int i = index;
while (i < j) {
swap(a[i], a[j]);
i += 1;
j -= 1;
}
return true;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (next_permutation(n, a)) {
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}
else
cout << -1 << '\n';
return 0;
}이전 순열
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool prev_permutation(int n, vector<int>& a) {
int index = n - 1;
while (index > 0 && a[index - 1] <= a[index]) index -= 1;
if (index == 0) return false;
int j = n - 1;
while (a[j] >= a[index - 1]) j -= 1;
swap(a[index - 1], a[j]);
j = n - 1;
int i = index;
while (i < j) {
swap(a[i], a[j]);
i += 1;
j -= 1;
}
return true;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (prev_permutation(n, a)) {
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}
else
cout << -1 << '\n';
return 0;
}https://www.acmicpc.net/problem/10974
모든 순열
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 1; i <= n; i++) {
a[i - 1] = i;
}
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
while (next_permutation(a.begin(), a.end())) {
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}
return 0;
}https://www.acmicpc.net/problem/10819
차이를 최대로
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
bool next_permutation(int n, vector<int>& a) {
int index = n - 1;
while (index > 0 && a[index - 1] >= a[index]) {
index -= 1;
}
if (index == 0) {
return false;
}
int j = n - 1;
while (a[j] <= a[index - 1]) {
j -= 1;
}
swap(a[index - 1], a[j]);
j = n - 1;
int i = index;
while (i < j) {
swap(a[i], a[j]);
i += 1;
j -= 1;
}
return true;
}
int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a.begin(), a.end());
int ans = 0;
do {
int temp = 0;
for (int i = 0; i < n - 1; i++) {
temp += abs(a[i] - a[i + 1]);
}
if (temp > ans) {
ans = temp;
}
} while (next_permutation(n, a));
printf("%d\n", ans);
return 0;
}https://www.acmicpc.net/problem/10971
외판원 순회 2
시간 복잡도가 N x N!로 나오는데 N의 최대 값이 10이므로 O(3천만)으로 가능하다.
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 20000000
using namespace std;
int d[10][10];
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> d[i][j];
}
}
int ans = MAX;
do {
int temp = 0;
for (int i = 0; i < n - 1; i++) {
temp += d[a[i]][a[i + 1]];
if (d[a[i]][a[i + 1]] == 0)
temp += MAX;
}
temp += d[a[n - 1]][a[0]];
if (d[a[n - 1]][a[0]] == 0) {
temp += MAX;
}
if (ans > temp) {
ans = temp;
}
if (temp < ans) ans = temp;
} while (next_permutation(a.begin(), a.end()));
cout << ans << endl;
return 0;
}염주 순열, 시작점이 같아도 된다
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[20][20];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
vector<int> d(n);
for (int i=0; i<n; i++) {
d[i] = i;
}
int ans=2147483647;
do {
bool ok = true;
int sum = 0;
for (int i=0; i<n-1; i++) {
if (a[d[i]][d[i+1]] == 0) {
ok = false;
} else {
sum += a[d[i]][d[i+1]];
}
}
if (ok && a[d[n-1]][d[0]] != 0) {
sum += a[d[n-1]][d[0]];
if (ans > sum) ans = sum;
}
} while (next_permutation(d.begin()+1, d.end()));
printf("%d\n",ans);
return 0;
}https://www.acmicpc.net/problem/6603
로또 (컴비네이션의 구현, next_permutation으로 구현 가능)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
while(true) {
cin >> n;
if (n == 0) break;
vector<int> d(n);
for (int i = 0; i < n; i++) {
cin >> d[i];
}
vector<int> a(n);
for (int i = 0; i < n; i++) {
if (i < 6) a[i] = 1;
else a[i] = 2;
}
do {
for (int i = 0; i < n; i++) {
if (a[i] == 1)
cout << d[i] << ' ';
}
cout << '\n';
} while (next_permutation(a.begin(), a.end()));
cout << '\n';
}
return 0;
}https://www.acmicpc.net/problem/14888
연산자 끼워넣기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> d(n);
for (int i = 0; i < n; i++) {
cin >> d[i];
}
vector<int> a;
for (int i = 1; i <= 4; i++) {
int t;
cin >> t;
for (int j = 0; j < t; j++) {
a.push_back(i);
}
}
vector<int> ans;
do {
int temp = d[0];
for (int i = 0; i < a.size(); i++) {
switch (a[i]) {
case 1: temp += d[i + 1];
break;
case 2: temp -= d[i + 1];
break;
case 3: temp *= d[i + 1];
break;
case 4: temp /= d[i + 1];
break;
default:
break;
}
}
ans.push_back(temp);
} while (next_permutation(a.begin(), a.end()));
sort(ans.begin(), ans.end());
cout << *(ans.end() - 1) << '\n' << *ans.begin() << '\n';
return 0;
}벡터 출력시 end() - 1 임에 주의하자
Recursive
다이나믹 프로그래밍에서 다시 다룬다.
재귀 유의할 사항
(1) 종료 조건
(2) 맞출 경우
(3) 그 외 경우(진행)
https://www.acmicpc.net/problem/9095
1, 2, 3 더하기
#include <iostream>
using namespace std;
int go(int sum, int goal);
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = go(0, n);
cout << ans << '\n';
}
return 0;
}
int go(int sum, int goal) {
if (sum > goal) return 0;
if (sum == goal) return 1;
int now = 0;
for (int i = 1; i <= 3; i++) {
now += go(sum + i, goal);
}
return now;
}https://www.acmicpc.net/problem/1759
암호 만들기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int l, c;
bool check(string &word) {
int ja = 0;
int mo = 0;
for (char x : word) {
if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u')
mo += 1;
else
ja += 1;
}
return (mo >= 1 && ja >= 2);
}
void go(int l, vector<char>& a, string word, int index) {
if (word.length() == l) {
if (check(word)) {
cout << word << '\n';
}
return;
}
if (index >= c)
return;
go(l, a, word + a[index], index + 1);
go(l, a, word, index + 1);
}
int main() {
cin >> l >> c;
vector<char> a(c);
for (int i = 0; i < c; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
go(l, a, "", 0);
return 0;
}뽑을까 말까 결정하기
https://www.acmicpc.net/problem/6603
로또(재귀로 풀기) - 이전과 마찬가지로 뽑을까 말까를 결정 길이가 되면 끝
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int k;
vector<int> lotto;
void go(vector<int>& a, int index) {
if (lotto.size() == 6) {
for (int num : lotto) {
cout << num << ' ';
}
cout << '\n';
return;
}
if (index >= a.size())
return;
lotto.push_back(a[index]);
go(a, index + 1);
lotto.pop_back();
go(a, index + 1);
}
int main() {
while (true) {
cin >> k;
if (k == 0) break;
vector<int> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i];
}
go(a, 0);
cout << '\n';
}
return 0;
}전역으로 선언 = 넣어줬으면 다시 빼줘야함, 리턴될 때 차근차근 하나씩 뺀다.
https://www.acmicpc.net/problem/1182
부분수열의 합
공집합인 경우 주의, 반드시 끝까지 가야 모든 경우 확인 가능
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, s;
int go(vector<int>& a, int sum, int index) {
if (index == n) { // 어차피 안더하는 경우가 있으므로 끝까지..
if (sum == s) return 1;
else return 0;
}
int now = 0;
now += go(a, sum + a[index], index + 1);
now += go(a, sum, index + 1);
return now;
}
int main() {
cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = go(a, 0, 0);
if (s == 0)
ans -= 1; // 공집합인 경우를 제 해야 해..
cout << ans << '\n';
return 0;
}https://www.acmicpc.net/problem/14501
퇴사
#include <iostream>
using namespace std;
int t[21];
int p[21];
int n;
int ans = 0;
void go(int day, int sum) {
if (day == n + 1) {
if (ans < sum) ans = sum;
return;
}
if (day > n) {
return;
}
go(day + 1, sum);
go(day + t[day], sum + p[day]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i] >> p[i];
}
go(1, 0);
cout << ans << '\n';
return 0;
}https://www.acmicpc.net/problem/14888
연산자 끼워넣기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, int> go(vector<int>& a, int index, int current, int plus, int minus,
int mul, int div) {
if (index == a.size()) {
return make_pair(current, current);
}
vector<pair<int, int>> result;
if (plus > 0) {
result.push_back(go(a, index + 1, current + a[index], plus - 1, minus
, mul, div));
}
if (minus > 0) {
result.push_back(go(a, index + 1, current - a[index], plus, minus - 1
, mul, div));
}
if (mul > 0) {
result.push_back(go(a, index + 1, current * a[index], plus, minus
, mul - 1, div));
}
if (div > 0) {
result.push_back(go(a, index + 1, current / a[index], plus, minus
, mul, div - 1));
}
auto ans = result[0];
for (auto p : result) {
if (ans.first < p.first) {
ans.first = p.first;
}
if (ans.second > p.second) {
ans.second = p.second;
}
}
return ans;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int p, min, mul, div;
cin >> p >> min >> mul >> div;
auto ans = go(a, 1, a[0], p, min, mul, div);
cout << ans.first << '\n' << ans.second << '\n';
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> result;
void go(vector<int>& a, int index, int current, int plus, int minus,
int mul, int div) {
if (index == a.size()) {
result.push_back(make_pair(current, current));
}
if (plus > 0) {
go(a, index + 1, current + a[index], plus - 1, minus
, mul, div);
}
if (minus > 0) {
go(a, index + 1, current - a[index], plus, minus - 1
, mul, div);
}
if (mul > 0) {
go(a, index + 1, current * a[index], plus, minus
, mul - 1, div);
}
if (div > 0) {
go(a, index + 1, current / a[index], plus, minus
, mul, div - 1);
}
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int p, min, mul, div;
cin >> p >> min >> mul >> div;
go(a, 1, a[0], p, min, mul, div);
auto ans = result[0];
for (auto p : result) {
if (ans.first < p.first) {
ans.first = p.first;
}
if (ans.second > p.second) {
ans.second = p.second;
}
}
cout << ans.first << '\n' << ans.second << '\n';
return 0;
}https://www.acmicpc.net/problem/15658
연산자 끼워넣기 (2)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> box;
void go(int index, int n, long long result,
vector<int> &a,int add, int min, int mul, int minu) {
if (index == n) {
box.push_back(result);
return;
}
if(add > 0)
go(index + 1, n, result + a[index], a, add - 1, min, mul, minu);
if(min > 0)
go(index + 1, n, result - a[index], a, add , min - 1, mul, minu);
if(mul > 0)
go(index + 1, n, result * a[index], a, add , min, mul - 1, minu);
if(minu > 0)
go(index + 1, n, result / a[index], a, add , min, mul, minu - 1);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> op(4);
for (int i = 0; i < 4; i++) {
cin >> op[i];
}
go(1, n, a[0], a, op[0], op[1], op[2], op[3]);
auto p = minmax_element(box.begin(), box.end());
cout << *p.second << endl;
cout << *p.first << endl;
return 0;
}.jpg)
SS