[C++] 브루트 포스(Brute Force)

브루트 포스(Brute Force)

연산이 1억회가 안 넘어갈 때 모든 경우의 수를 검사하는 알고리즘으로 완전 탐색이라고도 한다.

 

문제

 

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

#include <iostream>
#include <algorithm>
using namespace std;

bool board[50][50];

int compare(int x, int y, bool white)
{
	int cnt = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (white != board[x + i][y + j])
				cnt++;
			white = !white;
		}
		white = !white;
	}
	return cnt;
}

int main(void)
{
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			char c;
			cin >> c;

			if (c == 'W')
				board[i][j] = true;
		}

	int ans = 64;
	for (int i = 0; i < n - 7; ++i)
		for (int j = 0; j < m - 7; ++j)
			ans = min(ans, min(compare(i, j, true), compare(i, j, false)));

	cout << ans;
	return 0;
}

 

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

#include <iostream>
#include <string>
using namespace std;

int main(void)
{
	int n;
	cin >> n;

	int ans = 666, cnt = 0;
	while (n != 0) {
		string value = to_string(ans++);
		for (int j = 0; j < value.length() - 2; j++)
			if (value.substr(j, 3) == "666") {
				n--;
				if (n == 0)
					ans--;
				break;
			}
	}

	cout << ans;
	return 0;
}