[C++][백준][알고리즘] 브루트 포스 🎯

브루트 포스는 모든 경우의 수를 다 해보는 것이다.

예를 들어, 비밀번호가 4자리이고, 숫자로만 이루어져 있다고 한다면 0000부터 9999까지 다 입력해보면 된다.
비밀번호 4자리의 경우의 수는 10,000가지 이다.

브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다.
1. 문제의 가능한 경우의 수를 계산해본다.
2. 가능한 모든 방법을 다 만들어본다.
3. 각각의 방법을 이용해 답을 구해본다

 

경우의 수

N명의 사람이 한 줄로 서는 경우의 수 → N × (N-1) × … × 1 = N!
N명의 사람 중에서 대표 두 명을 뽑는 경우의 수 → N × (N-1) / 2
N명의 사람 중에서 대표 세 명을 뽑는 경우의 수 → N × (N-1) × (N-2) / 3!
N명의 사람 중에서 반장 1명과 부반장 1명을 뽑는 경우의 수 → N × (N-1)
N명의 사람이 있을 때, 각 사람이 영화를 볼지, 보지 않을지 결정한다. 가능한 조합의 수 → 2N

 

2309번

2309번: 일곱 난쟁이

• 아홉명 중에 일곱 명을 고르는 것은, 아홉 명 중에 두 명을 고르는 것과 같은 문제입니다. 고르는 개수의 차이만 있을 뿐 접근하는 방식은 동일합니다.

 

// Online C++ compiler to run C++ program online
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool ch[9];
int arr[9];
int sel[9];
bool isFinish = false;

void dfs(int s, int p)
{
    if(isFinish)
        return;
    
    if(p == 7)
    {
        int sum = 0;
        for(int i = 0; i < 7; ++i)
            sum += arr[sel[i]];
            
        if(sum == 100)
        {
            vector<int> res;
            for(int i = 0; i < 7; ++i)
                res.push_back(arr[sel[i]]);
            sort(res.begin(), res.end());
            for(int i = 0; i < 7; ++i)
                printf("%d\n", res[i]);
            isFinish = true;
        }

    }
    else
    {
        for(int i = 0; i < 9; ++i)
        {
            if(!ch[i])
            {
                ch[i] = true;
                sel[p] = i;
                dfs(s + 1, p + 1);
                ch[i] = false;
            }
        }
    }
}

int main() {
    for(int i = 0; i < 9; ++i)
        scanf("%d", &arr[i]);
        
    dfs(0, 0);

    return 0;
}

• DFS를 이용하여 9개 중 7개를 선택하는 조합을 구하는 알고리즘을 사용하여 문제를 해결하였습니다. 7개를 골랐다면, 그 요소들의 합이 100인지 검사하여 마무리합니다.

 

3085번

3085번: 사탕 게임

• N^2크기의 배열에서 상하좌우 원소를 서로 swap하여 가장 긴 행, 열의 크기를 리턴하는 문제입니다.

 

// Online C++ compiler to run C++ program online
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

char board[50][50];
int N;
int ans = INT_MIN;

int dx[4] { -1, +1, 0 ,0 };
int dy[4] { 0, 0, -1, +1 };

void check() {
	char c;
	
	// 행 계산
	for (int i = 0; i < N; i++) 
	{
		int count = 1; // 1개부터 시작
		c = board[i][0]; // 시작은 행의 첫번째 원소부터
		for (int j = 1; j < N; j++) 
		{
		    // c와 같은 char라면, 연속된 길이
			if ((board[i][j] == c))
				++count;
			else 
			    count = 1;
		    
		    // 연속에 상관 없이 다음 c는 현재 위치의 char
			c = board[i][j];
			
			// 개수 갱신
			ans = max(ans, count);
		}
	}

	// 열 계산
	for (int i = 0; i < N; i++) 
	{
		int count = 1; // 1개부터 시작
		c = board[0][i];
		for (int j = 1; j < N; j++) 
		{
			if ((board[j][i] == c))
				++count;
			else 
			    count = 1;
			    
			c = board[j][i];
			
			ans = max(ans, count);
		}
	}
}

int main() {
    cin >> N;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            cin >> board[i][j];
            
    for(int y = 0; y < N; ++y) // col
        for(int x = 0; x < N; ++x) // row
            for(int k = 0; k < 4; ++k) // 4 path
            {
                // 각 방향을 구하기
                int ddy = y + dy[k];
                int ddx = x + dx[k];
                
                // 벗어난경우 무시
                if(ddy < 0 || ddx < 0 || ddy == N || ddx == N)
                    continue;
                    
                // swap 후 개수를 계산한 후 다시 되돌리기
                swap(board[y][x], board[ddy][ddx]);
                check();
                swap(board[y][x], board[ddy][ddx]);
            }
            
    printf("%d", ans);

    return 0;
}

• dx, dy를 이용하여 네 방향에 swap을 하고, check를 통해 연속된 가장 긴 길이를 리턴합니다.
• swap을 한 후에는 다시 swap을 하여 원상태를 유지합니다.

 

1476번

1476번: 날짜 계산

#include <iostream>
using namespace std;

int main() {

    int year = 1;
    
    int E, S, M;
    cin >> E >> S >> M;
    
    int e = 1, s = 1, m = 1;

    for(int i = 1; i <= 7980; ++i)
    {
        if(e == E && s == S && m == M)
        {
            printf("%d", i);
            break;
        }
        
        ++e;
        ++s;
        ++m;
        
        if(e == 16)
            e = 1;
        if(s == 29)
            s = 1;
        if(m == 20)
            m = 1;
    }

    return 0;
}

• 이 문제는 총 경우의 수를 파악하는것이 중요한 문제입니다.
• 가능한 총 경우의 수는 15 * 28 *19로 7980에 해당합니다. e가 15, s가 28, m이 19에 해당할 때 마지막 값이 됩니다.
• 1부터 7890까지 반복하여 조건에 따라 e, s, m을 변경해주어 입력값과 일치해지면 정답을 출력합니다.

 

1107번

1107번: 리모컨

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <climits>
using namespace std;

// 선택 가능한 모든 버튼
vector<int> numbers { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// DFS에서 선택한 원소의 번호
int sel[10] { 0, };

// 입력
int N = 0, M = 0;

// 정답
int answer = INT_MAX;

void dfs(int s, int length)
{
    // length만큼 골랐다면?
    if(s == length)
    {
        int num = 0;
       
       // 앞에서부터 조립하여 숫자 생성 
        for(int i = 0; i < length; ++i)
            num += (pow(10, length - i - 1) * numbers[sel[i]]);
            
        // 최소값 갱신
        answer = min(answer, length + abs(N - num));
    }
    else
    {
        // 0부터 중복하여 선택
        for(int i = 0; i < numbers.size(); ++i)
        {
            sel[s] = i;
            dfs(s + 1, length);
        }
    }
}

int main() {
    int input;

    cin >> N >> M;
    
    for(int i = 0; i < M; ++i)
    {
        cin >> input;
        numbers.erase(find(numbers.begin(), numbers.end(), input));
    }
    
    // 모든 버튼이 망가진경우?
    if(M == 10)
    {
        cout << abs(100 - N);
        return 0;
    }
    
    // 모든 버튼이 망가지지 않은경우?
    if(M == 0)
    {
        cout << min((int)to_string(N).size(), abs(100 - N));
        return 0;
    }    

    int length = to_string(N).size();
    
    // 요구 자리 수 - 1
    if(length > 1)
        dfs(0, length - 1);
    
    // 요구 자리 수    
    dfs(0, length);
    
    // 요구 자리 수 + 1
    dfs(0, length + 1);

    cout << min(answer, abs(100 - N));

    return 0;
}

• DFS를 활용하여 문제를 해결하였습니다. 선택 가능한 버튼에서 M개를 제외한 나머지 중 N의 자리수만큼 중복을 허용하여 선택을 합니다.
• 선택된 값에서 N을 빼어 최소값을 갱신할 수 있습니다.
• 문제 자체는 간단하다고 생각하였으나, 내부적으로 고려해야 할 다양하고 복잡한 조건이 있어 실수가 있었습니다.

글 읽기 - ****리모컨 질문게시판에있는 모든 반례 모음****

 

#include <iostream>
using namespace std;
bool broken[10];
int possible(int c) {
    if (c == 0) {
        if (broken[0]) {
            return 0;
        } else {
            return 1;
        }
    }
    int len = 0;
    while (c > 0) {
        if (broken[c % 10]) {
            return 0;
        }
        len += 1;
        c /= 10;
    }
    return len;
}
int main() {
    int n;
    cin >> n;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        broken[x] = true;
    }
    int ans = n - 100;
    if (ans < 0) {
        ans = -ans;
    }
    for (int i = 0; i <= 1000000; i++) {
        int c = i;
        int len = possible(c);
        if (len > 0) {
            int press = c - n;
            if (press < 0) {
                press = -press;
            }
            if (ans > len + press) {
                ans = len + press;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

• 더욱 효율적인 코드로, DFS를 사용하지 않고, 0부터 1000000까지 반복하여 해당 i에 고장난 버튼이 포함되어있는지 검사하여 나아가는 방법입니다.

 

14500번

14500번: 테트로미노

#include <iostream>

int main() {
    
    int N, M;
    int arr[500][500];
    
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            scanf("%d", &arr[i][j]);
            
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            /*
                🟥🟥🟥🟥
            */
            if (j+3 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i][j+3];
                if (ans < temp) ans = temp;
            }
            /*
                🟥
                🟥
                🟥
                🟥
            */
            if (i+3 < N) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+3][j];
                if (ans < temp) ans = temp;
            }
            /*
                🟥
                🟥🟥🟥
            */
            if (i+1 < N && j+2 < M) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            /*
                🟥🟥
                🟥
                🟥
            */            
            if (i+2 < N && j+1 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+2][j];
                if (ans < temp) ans = temp;
            }
            /*
                🟥🟥🟥
                    🟥
                
            */               
            if (i+1 < N && j+2 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            /*
                  🟥
                  🟥
                🟥🟥
            */             
            if (i+2 < N && j-1 >= 0) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            /*
                    🟥
                🟥🟥🟥
            */              
            if (i-1 >= 0 && j+2 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            /*
                🟥
                🟥
                🟥🟥
            */               
            if (i+2 < N && j+1 < M) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            /*
                🟥🟥🟥
                🟥
            */               
            if (i+1 < N && j+2 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j];
                if (ans < temp) ans = temp;
            }
            /*
                🟥🟥
                  🟥
                  🟥
            */              
            if (i+2 < N && j+1 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            /*
                🟥🟥
                🟥🟥
            */                 
            if (i+1 < N && j+1 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1];
                if (ans < temp) ans = temp;
            }
            /*
                  🟥🟥
                🟥🟥
            */               
            if (i-1 >= 0 && j+2 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i-1][j+1] + arr[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            /*
                🟥
                🟥🟥
                  🟥
            */               
            if (i+2 < N && j+1 < M) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            /*
                🟥🟥
                  🟥🟥
            */              
            if (i+1 < N && j+2 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            /*
                  🟥
                🟥🟥
                🟥
            */              
            if (i+2 < N && j-1 >= 0) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+1][j-1] + arr[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            /*
                  🟥
                🟥🟥🟥
                
                🟥🟥🟥
                  🟥
            */ 
            if (j+2 < M) {
                int temp = arr[i][j] + arr[i][j+1] + arr[i][j+2];
                if (i-1 >= 0) {
                    int temp2 = temp + arr[i-1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (i+1 < N) {
                    int temp2 = temp + arr[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
            }
            /*
                  🟥
                🟥🟥
                  🟥
                  
                🟥
                🟥🟥
                🟥
            */             
            if (i+2 < N) {
                int temp = arr[i][j] + arr[i+1][j] + arr[i+2][j];
                if (j+1 < M) {
                    int temp2 = temp + arr[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (j-1 >= 0) {
                    int temp2 = temp + arr[i+1][j-1];
                    if (ans < temp2) ans = temp2;
                }
            }
        }
    }
    
    printf("%d", ans);
    return 0;
}

• N*M만큼 반복하여 해당 위치에 가능한 모든 모양의 테트로미노에 해당하는 위치에서 값을 계산하여 최고값을 갱신합니다.
• 문제 자체는 간단하지만, 19개의 테트로미노 모양에 대한 조건식을 정확하게 써야 오류가 나지 않습니다.
  • 실수를 한 경우에 디버깅이 어렵습니다.

 

#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {
    {{0,1}, {0,2}, {0,3}},
    {{1,0}, {2,0}, {3,0}},
    {{1,0}, {1,1}, {1,2}},
    {{0,1}, {1,0}, {2,0}},
    {{0,1}, {0,2}, {1,2}},
    {{1,0}, {2,0}, {2,-1}},
    {{0,1}, {0,2}, {-1,2}},
    {{1,0}, {2,0}, {2,1}},
    {{0,1}, {0,2}, {1,0}},
    {{0,1}, {1,1}, {2,1}},
    {{0,1}, {1,0}, {1,1}},
    {{0,1}, {-1,1}, {-1,2}},
    {{1,0}, {1,1}, {2,1}},
    {{0,1}, {1,1}, {1,2}},
    {{1,0}, {1,-1}, {2,-1}},
    {{0,1}, {0,2}, {-1,1}},
    {{0,1}, {0,2}, {1,1}},
    {{1,0}, {2,0}, {1,1}},
    {{1,0}, {2,0}, {1,-1}},
};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            for (int k=0; k<19; k++) {
                bool ok = true;
                int sum = a[i][j];
                for (int l=0; l<3; l++) {
                    int x = i+block[k][l][0];
                    int y = j+block[k][l][1];
                    if (0 <= x && x < n && 0 <= y && y < m) {
                        sum += a[x][y];
                    } else {
                        ok = false;
                        break;
                    }
                }
                if (ok && ans < sum) {
                    ans = sum;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• 위 정답보다 보다 개선된 형태로, 3차원 배열에 0,0을 기준으로하여 상대적인 위치에 나머지 세개의 블록을 두는 방식으로 구현한 방식입니다.

 

6064번

6064번: 카잉 달력

#include <iostream>
using namespace std;
int main() {
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        int M, N, X, Y;
        cin >> M >> N >> X >> Y;
        
        --X, --Y;
        // 1씩 빼면 나머지를 활용하여 문제를 해결할 수 있음
        // X와 Y중 하나를 고정하여 문제를 해결하기
        // X를 고정한다고 가정했을 때, Y의 값을 찾아 정답을 구하기
        
        /*
            1을 빼지 않았을 때
            • 1: <1,1>
            • 2: <2,2>
            • 3: <3,3>
            • 4: <4,4>
            • 5: <5,5>
            • 6: <1,6>
            • 7: <2,7>
            • 8: <3,1>
            • 9: <4,2>
            • 10: <5,3>
            
            1을 빼면 X, Y중 하나를 고정하여 해결 가능
            0부터 X, Y는 차례대로 루프로 고정됨
            • 0: <0,0>
            • 1: <1,1>
            • 2: <2,2>
            • 3: <3,3>
            • 4: <4,4> (첫 사이클 동안은 값이 동일함)
            • 5: <0,5>
            • 6: <1,6>
            • 7: <2,0>
            • 8: <3,1>
            • 9: <4,2>
            • 10: <0,3>
        */
        
        // 조합을 찾았는가?
        bool ok = false;
        
        // int k = X를 하는 이유는 첫 X의 값과 Y는 동일하기 때문
        // 
        // k += M을 하는 이유는 M을 더하면 X축이 고정되는 원리
        // k += M을 하여 고정된 축에서 k % M == Y라면, 해당 조합을 찾은 것
        for (int k = X; k < (N * M); k += M) 
        {
            if (k % N == Y) 
            {
                cout << k + 1 << '\n';
                ok = true;
                break;
            }
        }
        if (!ok)
            cout << -1 << '\n';

    }
    return 0;
}

• 1씩 빼면 나머지를 활용하여 문제를 해결할 수 있습니다. 이는 날짜계산 문제와 비슷합니다.

 

1748번

1748번: 수 이어 쓰기 1

#include <iostream>
#include <cmath>

int sizes[9] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int main() {
    long long int answer = 0;
    int N;
    scanf("%d", &N);
    
    int digit = 1;
    for(; digit <= 10; ++digit)
    {
        if(!(N / (int)pow(10, digit - 1)))
        {
            --digit;
            break;
        }
    }
    
    for(int i = 1; i < digit; ++i)
        answer += (pow(10, i) - pow(10, i - 1)) * i;

    answer += (N - (int)pow(10, digit - 1) + 1) * sizes[digit - 1];
       
    printf("%lld", answer);
}

• digit를 구하여 자리수-1까지 9 * 10^n만큼 더합니다.
  • 한자리는 9, 두자리는 90, 세자리는 900...으로 증가합니다.
• 마지막 digit는 꽉 차있지 않기 때문에 pow(10, digit - 1)를 빼주어 해당 자리수의 크기만큼 곱하여 정답을 리턴합니다.