[BOJ/C++] 단계별로 풀어보기 - 브루트 포스

#cpp #programming #coding

2026.01.08일차 입니다. 브루트 포스 풀어보았습니다.

브루트 포스란?

브루트 포스(Brute Force)란 무차별 대입이라고도 부르며 모든 경우의 수를 대입하여 답을 찾는 방법입니다.
모든 경우의 수를 탐색하므로 정확성은 높으나 복잡도에 매우 민감하다는 치명적인 단점이 있습니다.
주로 반복문과 조건문을 통하여 답을 도출합니다.

2798번 블랙잭

문제 링크
^NC³ 문제이므로 세 개의 반복문을 통해 구현해야 합니다.

중복 없는 세 장을 구하기 위해서 0≤i＜N-2, i+1≤j＜N-1, j+1≤k＜N의 인덱스로 구성해야 합니다.

#include <iostream>
using namespace std;
int main() {
    int N, M, r = 0; cin >> N >> M; int* arr = new int[N]; for (int i = 0; i < N; ++i) cin >> arr[i];
    for (int i = 0; i < N - 2; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
            for (int k = j + 1; k < N; ++k) { int t = arr[i] + arr[j] + arr[k]; r = t > r && t <= M ? t : r; }
        }
    } cout << r;
}

서로 다른 세 장의 카드를 더한 값이 M 이하인 값 중 최댓값을 도출하면 됩니다.

2231번 분해합

문제 링크

#include <iostream>
using namespace std;
int main() {
    int N, r = 0; cin >> N;
    for (int i = 1; i < N; ++i) {
        int a = i, b = i; while (a) { b += a % 10; a /= 10; }
        if (b == N) { r = i; break; }
    } cout << r;
}

1부터 N-1까지의 값을 자기 자신에 각 자릿수를 더한 값을 계산합니다. 그 값이 N과 같은지 판단합니다. 각 자릿수는 10으로 나눈 나머지를 통해 얻을 수 있습니다.

19532번 수학은 비대면강의입니다.

문제 링크

#include <iostream>
using namespace std;
int main() {
    int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
    for (int x = -999; x <= 999; ++x) {
        for (int y = -999; y <= 999; ++y) {
            if (a * x + b * y == c && d * x + e * y == f) { cout << x << ' ' << y; break; }
        }
    }
}

x, y의 범위가 한정되어 있는 평범한 브루트 포스 문제입니다.

#include <iostream>
using namespace std;
int main() {
    int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
    cout << (c * e - b * f) / (a * e - b * d) << ' ' << (a * f - d * c) / (a * e - b * d);
}

그런데 이 문제는 브루트 포스를 쓰지 않고도 풀 수 있습니다.

1018번 체스판 다시 칠하기

문제 링크

#include <iostream>
using namespace std;
int main() {
    int N, M, r = 65; cin >> N >> M; char** a = new char* [N];
    for (int i = 0; i < N; ++i) { a[i] = new char[M]; for (int j = 0; j < M; ++j) cin >> a[i][j]; }
    char w[8][8] = { {'W','B','W','B','W','B','W','B'}, {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'}, {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'}, {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'}, {'B','W','B','W','B','W','B','W'} };
    char b[8][8] = { {'B','W','B','W','B','W','B','W'}, {'W','B','W','B','W','B','W','B'},
        {'B','W','B','W','B','W','B','W'}, {'W','B','W','B','W','B','W','B'},
        {'B','W','B','W','B','W','B','W'}, {'W','B','W','B','W','B','W','B'},
        {'B','W','B','W','B','W','B','W'}, {'W','B','W','B','W','B','W','B'}, };
    for (int i = 0; i < N - 7; ++i) {
        for (int j = 0; j < M - 7; ++j) {
            int t = 0; for (int x = 0; x < 8; ++x) {
                for (int y = 0; y < 8; ++y) {
                    t += !(a[i + x][j + y] == w[x][y]);
                }
            } r = t < r ? t : r;
            t = 0; for (int x = 0; x < 8; ++x) {
                for (int y = 0; y < 8; ++y) {
                    t += !(a[i + x][j + y] == b[x][y]);
                }
            } r = t < r ? t : r;
        }
    } cout << r;
}

프리셋을 정해두고 배열을 8*8 범위로 탐색하며 프리셋과 비교합니다.
최솟값을 찾아야 하므로 초기 값을 최댓값인 8*8+1 = 65로 설정합니다.
탐색을 하며 최솟값을 갱신합니다.

또는 인덱스의 합을 통해 풀 수 있으며 해당 블로그를 참고하였습니다.

인덱스의 홀짝에 따라 체스판 색이 다른 성질을 이용했습니다.

#include <iostream>
using namespace std;
int main() {
    int N, M, r = 65; cin >> N >> M; char** a = new char* [N];
    for (int i = 0; i < N; ++i) { a[i] = new char[M]; for (int j = 0; j < M; ++j) cin >> a[i][j]; }

    for (int i = 0; i < N - 7; ++i) {
        for (int j = 0; j < M - 7; ++j) {
            int w = 0, b = 0; for (int x = 0; x < 8; ++x) {
                for (int y = 0; y < 8; ++y) {
                    if ((x + y) % 2 == 0) { if (a[i + x][j + y] != 'W') ++w; else ++b; }
                    else { if (a[i + x][j + y] != 'B') ++w; else ++b; }
                }
            } r = w < r ? w : r; r = b < r ? b : r;
        }
    } cout << r;
}

코드는 다음과 같습니다.

1436번 영화감독 숌

문제 링크

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    int N, i = 0, a = 665; cin >> N;
    while (i < N) {
        ++a; string b = to_string(a);
        if (b.find("666") != string::npos) ++i;
    } cout << a;
}

666부터 시작합니다. to_string을 통해 숫자를 string 문자열로 변환 후 문자열 내에 "666"이 있다면 카운팅 합니다. 다시 보니 i = 1, a = 666 이렇게 했어도 됐었는데 생각을 하지 못했습니다.

2839번 설탕 배달

문제 링크
5kg 봉지가 가장 많은 경우가 봉지의 수가 가장 적은 경우이므로 5kg 봉지가 가장 많은 경우부터 살펴봅니다.

#include <iostream>
using namespace std;
int main() {
    int N, r = -1; cin >> N;
    for (int i = N / 5; i >= 0; --i) {
        int t = N - i * 5; if (t % 3 == 0) { r = i + t / 3; break; }
    } cout << r;
}