브루트포스 코드 작성해보기

브루트포스란?

가능한 모든 경우의 수를 전부 시도해보는 것. 무식하게 문제를 푸는 것이라고 할 수 있다.

 

예제 문제 1)

정수 n(1 <= n <= 100)이 주어질 때, 다음 식을 만족하는 (a, b, c)의 개수를 구하라. 단 a, b, c는 1이상 100이하인 자연수로 가정하고, a, b, c가 중복될 수 있음.

 

코드

int count = 0;
for (int a = 1; a <= 100; a++) {
    for (int b = 1; b <= 100; b++) {
        for (int c = 1; c <= 100; c++) {
            if (a + b*b + c*c*c == n) {
                count++;
            }
        }
    }
}
cout << count;

중복을 포함해서 브루트푸스를 사용한 방식이다. 모두 100번을 순회하면서, a 와 b * b + c * c * c가 n과 같다면, count의 수를 더해준다.

 

예제 문제 2)

정수 n (1 <= n <= 100)이 주어질 때, 다음 식을 만족하는 (a, b, c)의 개수를 구하는 문제를 불필요한 중복 제거를 하여 풀어보기. [ a + b ^ 2 + c ^ 3 = n]

 

코드

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

int main()
{
	//정수 n이 주어질 때, 
	int n;
	cin >> n;
	int count = 0;

	for (int c = 1; c * c * c <= n; c++)
	{
		for (int b = 1; b * b <= n; b++)
		{
			if (n - (b * b) + (c * c * c) > 0)
			{
				++count;
			}
		}
	}

	cout << count << endl;
	return 0;
}

먼저 첫번째 수가 진행될때, c ^ 3 한 값이 n을 넘지않을 만큼만 순회해준다. 그리고 두번째로 b ^ 2의 값이 n을 넘지 않게 순회한 다음에 n에서 b ^ 2와 c^3을 한 값이 0 이상이면 count의 값이 늘어나게 해주었다.