[BOJ] 브루트 포스

오늘부터는 (시시한 거 그만하고) 슬슬 알고리즘을 해보도록 하겠습니다. 오늘의 주제는 브루트 포스입니다. 브루트 포스는 그냥 무식하게 하나하나 다 해보는 방법입니다. 한마디로 난 그런 거 잘 모르겠고 일단 부딪혀.

 

[BOJ 2798]

 

3개의 카드를 고르는 경우를 모두 해보는 방법입니다. 3개의 카드를 고르기 때문에 3중 for문입니다.

#include <stdio.h>
#include <vector>

using namespace std;

int nearestsum(const vector<int> & cards, int limit){
    int maxsum = 0;
    for(int i=0;i<cards.size();++i)
    for(int j=i+1;j<cards.size();++j)
    for(int k=j+1;k<cards.size();++k){
        int newsum = cards[i] + cards[j] + cards[k];
        if(maxsum < newsum && newsum <= limit)
            maxsum = newsum;
    }
    return maxsum;
}

int main(){
    int N, M;
    scanf("%d%d",&N,&M);
    vector<int> cards(N);
    for(int k=0;k<N;++k)
        scanf("%d",&cards[k]);
    printf("%d",nearestsum(cards,M));
}

 

[BOJ 2231]

 

브루트 포스에 충실하게 숫자의 분해합을 구하는 함수를 짜고 하나씩 해보면서 값을 찾습니다.

#include <stdio.h>

int dividesum(int N){
    int divsum = N;
    while(N != 0){
        divsum += (N % 10);
        N /= 10;
    }
    return divsum;
}

int main(){
    int N;
    scanf("%d",&N);
    int m = 1;
    while(dividesum(m) != N && m<=N) m++;
    printf("%d", m<=N ? m : 0);
}

 

[BOJ 7568]

 

처음에는 이게 뭔가 싶었습니다. 결국에는 이 문장에 충실하게 해 주면 되겠습니다.

 

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. -본문 발췌-

 

한 명씩 덩치가 큰 사람을 세어주면 됩니다.

#include <stdio.h>
#include <vector>

using namespace std;

typedef pair<int, int> physical_t;

bool comparephysical(const physical_t & a, const physical_t & b){
    return ((a.first > b.first) && (a.second > b.second));
}

vector<int> physicalrank(const vector<physical_t> & P){
    vector<int> rank(P.size());
    for(int k=0;k<P.size();++k){
        int countsuperior = 0;
        const physical_t assess = P[k];
        for(const physical_t buddy : P){
            if(comparephysical(buddy, assess))
                countsuperior++;
        }
        rank[k] = countsuperior + 1;
    }
    return rank;
}

int main(){
    int N;
    scanf("%d",&N);
    vector<physical_t> P(N);
    for(int k=0;k<N;++k)
        scanf("%d%d", &P[k].first, &P[k].second);
    vector<int> rank = physicalrank(P);
    for(int k=0;k<N;++k) printf("%d ",rank[k]);
}

 

[BOJ 1018]

 

(0,0)에서 8x8을 잘랐을 때, (0,1)에서 8x8을 잘랐을 때,...

이렇게 자른 다음에 한 번씩 필요한 색칠의 개수를 세어주면 되겠습니다. 8x8을 복사하지 않고 배열 상에서 값을 얻어오도록 하게 위해 getval이라는 wrapper를 사용하였습니다. 그리고 한 가지 더 있는데요, 왼쪽 위가 검은색인 경우랑 흰색인 경우에 모든 칸의 색깔이 반대이기 때문에 각 경우에 색칠해야 하는 블록의 개수를 세면 합이 반드시 8x8의 총 칸의 개수인 64개입니다. 이를 이용해 주었습니다. 

#include <stdio.h>
#include <vector>

using namespace std;

typedef enum boardcolor_t{
    WHITE,
    BLACK,
    ERROR,
} boardcolor_t;

constexpr int BOARDSIZE = 8;
constexpr int BOARDBLOCKCOUNT = BOARDSIZE * BOARDSIZE;

typedef vector<vector<boardcolor_t>> chessboard_t;

class chessboardcut{
    public:
    const chessboard_t * Pboard;
    int offset_i, offset_j;
    int setoffset(int i, int j){
        offset_i = i;
        offset_j = j;
        return 0;
    }
    boardcolor_t getval(int i, int j){
        return (*Pboard)[offset_i+i][offset_j+j];
    }
    private:
    int colormodify(){
        int count = 0;
        for(int i=0;i<BOARDSIZE;++i)
        for(int j=0;j<BOARDSIZE;++j){
            // assume we will color upper left black
            boardcolor_t targetcolor = ((i+j)%2 == 0 ? BLACK : WHITE);
            if(targetcolor != getval(i, j))
                count++;
        }
        return (count <= (BOARDBLOCKCOUNT / 2) ? count : BOARDBLOCKCOUNT - count);
    }
    public:
    int mincolormodify(const chessboard_t & board){
        Pboard = &board;
        int sz_vert = board.size();
        int sz_hori = board[0].size();
        int minmodcount = BOARDBLOCKCOUNT;
        
        for(int i=0;i<sz_vert - BOARDSIZE + 1;++i)
        for(int j=0;j<sz_hori - BOARDSIZE + 1;++j){
            setoffset(i, j);
            int newmodcount = colormodify();
            if(minmodcount > newmodcount)
                minmodcount = newmodcount;
        }
        return minmodcount;
    }
};

int main(){
    int N, M;
    scanf("%d%d ",&N,&M);
    chessboard_t board;
    board.resize(N);
    for(int i=0;i<N;++i){
        board[i].resize(M);
        for(int j=0;j<M;++j){
            switch(getchar()){
                case 'W': board[i][j] = WHITE; break;
                case 'B': board[i][j] = BLACK; break;
                default: board[i][j] = ERROR; break;
            }
        }
        getchar(); // flush '\n'
    }
    chessboardcut C;
    printf("%d", C.mincolormodify(board));
}

 

[BOJ 1436]

 

당연하게도 더 쉽고 빠른 방법이 있겠지만 브루트 포스에 충실하게 해 주었습니다. 1부터 하나씩 올리면서 확인해줍니다. 

#include <stdio.h>

bool has666(int N){
    int countsix = 0;
    do {
        if(N % 10 == 6)
            countsix++;
        else
            countsix = 0;
        N /= 10;
        if(countsix >= 3)
            return true;
    } while(N != 0);
    return false;
}

int main(){
    int N;
    scanf("%d",&N);
    int nth_number;
    // stop at 10000th number
    for(int x=666, count=0;x<=2666799;x++){
        if(has666(x))
            count++;
        if(count == N){
            nth_number = x;
            break;
        }
    }
    printf("%d", nth_number);
}

 

감사합니다.^^