[단계별로 풀어보기] 브루트 포스

1. 블랙잭

#include <iostream>

using namespace std;

int n, m;
int card[100];
int cmax = 0;
int sum;
int path[100];
int used[100];

void run(int le) {
    
    if (le == 3) {
        sum = 0;

        for (int i = 0; i < 3; i++) {
            //cout << path[i]<<" ";
            sum += path[i];
        }

        
        //cout << sum << endl;

        if (cmax < sum && sum <= m) {
            cmax = sum;
        }
        return;
    }

    for (int i = 0; i < n; i++) {
        if (used[i] == 1) continue;
        used[i] = 1;
        path[le] = card[i];
        run(le + 1);
        used[i] = 0;
        path[le] = 0;
    }

    if (le == 0)
        cout << cmax;
}

int main() {

    cin >> n;
    cin >> m;

    for (int i = 0; i < n; i++) {
        cin >> card[i];
    }

    run(0);

    return 0;
}

2. 분해합

 - Test1. 재귀사용 - 시간초과

#include <iostream>
#include <cmath>

using namespace std;

int m=0; //자릿수 구하기
int n; //주어진 분해합의 최소생성자 찾기 
int path[8];
int mmin = 1000000;

void run(int le) {

    if (le == m) {
        int sum = 0;
        int s=0;
        for (int x = 0; x < m; x++) {
           // cout << path[x] << " ";
            sum += path[x];
            s += path[x] * pow(10, x);
        }

        if (sum + s == n) {
            if (mmin > s)
                mmin = s;
        }

        //cout << endl;
        
        return;
    }

    for (int i = 0; i <= 9; i++) {
        path[le] = i;
        run(le + 1);
        path [le]= 0;
    }

    return;

}

int main() {

    cin >> n;

    int tmp = n;
    while (tmp) {
        tmp /= 10;
        m++;
        }

    run(0);

    if (mmin == 1000000) cout << 0;
    else cout << mmin;

    return 0;
}

- Test2. 재귀함수 사용X

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int m=0; //자릿수 구하기
int n; //주어진 분해합의 최소생성자 찾기 
int path[8];
int mmin = 1000000;

int run(int le) {
    int sum=0;
    int tmp = le;
    while (tmp) {
        sum += tmp % 10;
        tmp /= 10;
    }

    return sum + le;
}

int main() {
    vector<int>vec;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        if (run(i) == n)
            vec.push_back(i);
    }

    if (vec.empty()) {
        cout << 0;
        return 0;
    }

    else {
        int size = vec.size();
        for (int i = 0; i < size; i++)
        {
            if (mmin > vec[i])
                mmin = vec[i];
        }
    }

    cout << mmin;
    return 0;
}

3. 덩치

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;
vector<pair<int, int>>vec;
vector<int> result;

int n;

void check(int i) {

    for (int x = 0; x < n; x++) {
        if (i == x)continue;
        if (vec[i].first < vec[x].first && vec[i].second < vec[x].second) {
            result[i]++;
        }
    }
}

int main() {
    int cm, kg;
    cin >> n;


    for (int i = 0; i < n; i++) {
        cin >> cm >> kg;
        vec.push_back(make_pair(cm, kg));
        result.push_back(1);
    }

    for (int i = 0; i < n; i++) {
        check(i);
    }

    for (int i = 0; i < n; i++) {
        cout << result[i] << " ";
    }

    return 0;
}

4. 체스판 다시 칠하기

 -> 비교함수부분 비교조건 앞으로 잘보자..

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int n, m; //n행, m열
char map[50][50];

char bkmap[9][9] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
};


char wtmap[9][9] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};

int check(int y, int x) {

    int bc = 0, wc = 0;

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if(map[y+i][x+j] != bkmap[i][j])bc++; //비교조건 확인..
            else if (map[y+i][x+j] != wtmap[i][j]) wc++;
        }
    }

    if (bc >= wc) return wc;
    else return bc;

}

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
    }

    int min = 100;

    for (int a = 0; a <= n - 8; a++) { //y
        for (int b = 0; b <= m - 8; b++) { //x
            int result = check(a, b);
            if (min >= result)
                min = result;
        }
    }

    cout << min;


    return 0;
}

5. 영화감독 숌

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

vector<int>vec;

void check(int i) {
    string tmp = to_string(i);

    if (tmp.find("666", 0) != -1)
        vec.push_back(i);

}

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

    int a = 666;
    while (1) {
        check(a);
        if (vec.size() == n)
            break;
        a++;
    }

    cout << vec.back();
    return 0;
    
}