[BOJ] 브루트 포스 2

📝1018번: 체스판 다시 칠하기

문제 설명

체스판 다시 칠하기

해결 방법

1. 입력에 필요한 2차원 배열을 동적할당
2. 다시 칠해야 하는 정사각형 개수의 최솟값은 (N * M) / 2 + 1 보다 작다
3. 사용하고자 하는 8 x 8 체스판의 가장 왼쪽 위가 1) B인 경우 2) W인 경우로 나뉜다
4. 체스판 한 칸을 좌표로 생각하면 1)일 때 x, y 좌표의 합이 짝수면 'B'를 칠해야 하고 홀수면 'W'를 칠해야 한다
5. 반복할 때마다 cnt < min일 때 min에 cnt를 넣어주면 결국 최솟값이 들어가게 된다
6. 2)도 똑같다 코드를 그대로 가져와서 'B', 'W'만 바꿔준다
7. 최솟값 min 출력

💻소스코드

#include <iostream>
using namespace std;

int main(void) {
    int N, M;

    // input
    cin >> N >> M;
    char** board = new char * [N];
	for (int i = 0; i < N; i++)
		board[i] = new char[M];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];
    
    int cnt = 0;
    int min = (N * M) / 2 + 1;  // 다시 칠해야 하는 정사각형 개수의 최솟값

    // #BWBW
    for(int i = 0; i <= N - 8; i++){
        for(int j = 0; j <= M - 8; j++){
            cnt = 0;
                for(int k = i; k < i + 8; k++){
                    for(int l = j; l < j + 8; l++){
                        if ((k + l) % 2 == 0){
                            if (board[k][l] != 'B')
                                cnt++;
                        }
                        else {
                            if (board[k][l] != 'W')
                                cnt++;
                        }
                    }
                }
            if (cnt < min)
                min = cnt;
        }
    }
    // #WBWB
    for(int i = 0; i <= N - 8; i++){
        for(int j = 0; j <= M - 8; j++){
            cnt = 0;
                for(int k = i; k < i + 8; k++){
                    for(int l = j; l < j + 8; l++){
                        if ((k + l) % 2 == 0){
                            if (board[k][l] != 'W')
                                cnt++;
                        }
                        else {
                            if (board[k][l] != 'B')
                                cnt++;
                        }
                    }
                }
            if (cnt < min)
                min = cnt;
        }
    }
    cout << min;
    return 0;
}  

📝1436번: 영화감독 숌

문제 설명

영화감독 숌

해결 방법

• 숫자 666부터 시작해서 1씩 증가시킨다.(브루트포스) 666이 포함되어 있으면 종말의 숫자이므로 N번째 작은 종말의 수를 찾아 출력한다.

1. 정수형 title 변수를 666으로 선언 및 초기화, cnt는 N번째 종말의 수를 찾기 위해 선언
2. 무한루프, string tmp 변수에 title을 문자열로 바꾸고 할당(숫자가 666을 포함하는지 찾기 위함)
3. 연속적으로 666이라는 숫자가 나타나면 종말의 수이므로 cnt++하고 break, break를 걸지 않으면 cnt가 여러번 증가하므로 무한루프를 빠져나오지 않는다.
4. N과 cnt가 같아지면 해당 title을 출력, title을 1씩 증가시키며 반복.

💻소스코드

#include <iostream>
#include <string>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    int title = 666, cnt = 0;
    while (true) {
        string tmp = to_string(title);
        for (int i = 0; i < tmp.size() - 2; i++) {
            if (tmp[i] == '6' && tmp[i + 1] == '6' && tmp[i + 2] == '6') {
                cnt++;
                break;
            }
        }
        if (N == cnt) {
            cout << title << "\n";
            break;
        }
        title++;
    }
    return 0;
}