[c++/백준 단계별 풀기] 12단계-브루트 포스

원래 8단계부터 이어서 하는 게 맞겠지만... 수학문제들은 당장 필요한 건 아닌 거 같아서 바로 넘어가기 ㄱㄱㄱ

 

브루트 포스

-가능한 모든 경우의 수를 검사해 보는 알고리즘이다.

항상 정확도 100%를 보장하지만 그만큼 시간이 오래 걸리는 단점이 있다.

 

---

 

2798) 블랙잭

→https://www.acmicpc.net/problem/2798

2798번: 블랙잭

#include <iostream>
using namespace std;

int main()
{
	int n, m, sum=0, max=0;
	int I, J, K;
	cin >> n >> m;
	int* arr = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = n - 2; j >= 0; j--) {
			if (j == i) continue;
			for (int k = n - 3; k >= 0; k--) {
				if (k == i || k == j) continue;

				sum = arr[i] + arr[j] + arr[k];
				if (sum<=m && sum>max) {
					max = sum;
				}
			}
		}
	}
	cout << max;

	return 0;
}

★3개의 카드를 뽑을 확률을 구할 때처럼, 각각 for문으로 반복하는데 중복이 없도록 조건을 작성한다. 근데 그렇게만 해도 중복이 생기길래 따로 if문으로 중간중간 검사해서 같으면 컨티뉴 하도록 하니까 됨
다른 풀이들 보니까 --로 안 하고 ++로 해서 i=0; j=1; k=2;식으로 하니까 검사 안 해도 중복 걸러지는 거 같음
그냥 순서만 반대로 했을 뿐인데 그게 되나?? 신기

 

---

2231) 분해합

→https://www.acmicpc.net/problem/2231

2231번: 분해합

#include <iostream>
using namespace std;

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

	for (int i = 1; i < n; i++) {
		int num=i, sum = i;
		while (num != 0) { 
			sum += num % 10;
			num /= 10;
		}
		if (sum == n) {
			cout << i;
			return 0;
		}
	}
	cout << 0;

	return 0;
}

★이 문제는 진짜 모르겠어서 그냥 찾아봤다...
일단 분해합은 무조건 1보다는 크고 생성자보다는 작으니까 그만큼 for문을 돌린다. 그러면서 차례대로 각 숫자마다 자기 자신을 sum에 더한 다음 그 숫자가 0이 될 때까지 10으로 나머지를 더하고 나눠서 각 자릿수를 더한다. 이때 더한 sum이 생성자와 같다면 출력하고 바로 종료한다. 종료가 안되면 0을 출력하고 끝낸다.

 

---

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

→https://www.acmicpc.net/problem/19532

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

#include <iostream>
using namespace std;

int main()
{
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;

	for (int i = -999; i <= 999; i++) {
		for (int j = -999; j <= 999; j++) {
			if (a * i + b * j == c) {
				if (d * i + e * j == f) {
					cout << i << " " << j;
					return 0;
				}
			}
		}
	}

	return 0;
}

☆수학식을 풀면 되는 문제인데, 위와 같이 그냥 다 탐색해서 구하는 방법이 있다. 처음엔 저걸 떠올리고... 그럼 시간초과가 나지 않나?라는 생각에 최소공배수를 구해서 하는 방법으로 하려다가... 이번 단계가 브루트 포스라는 것을 깨닫고... 역시나 다른 사람 풀이도 그냥 저렇게 풀길래 그렇게 했다. 따지고 보면 -999~999는 그다지 큰 범위가 아니어서 시간도 괜찮다고 한다.

 

---

1018) 체스판 다시 칠하기

→https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

#include <iostream>
#include<string>
#include<algorithm> //min 함수
using namespace std;

//두가지 경우의 올바른 체스판 설정
string WB[8];
string BW[8];
void setBoard() {
	for (int i = 0; i < 8; i++) {
		if (i % 2 == 0) {
			WB[i] = "WBWBWBWB";
			BW[i] = "BWBWBWBW";
		}
		else {
			WB[i] = "BWBWBWBW";
			BW[i] = "WBWBWBWB";
		}
	}
}
//W로 시작하는 체스판에서 다시 칠해야 되는 칸 계산
int wbCnt(int x, int y, string*board) {
	int cnt = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			//시작점(x,y)로부터 8칸까지 비교
			if (board[x + i][y + j] != WB[i][j]) cnt++;
		}
	}
	return cnt;
}
//B로 시작하는 체스판 계산에서 다시 칠해야 되는 칸 계산
int bwCnt(int x, int y, string* board) {
	int cnt = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			//시작점(x,y)로부터 8칸까지 비교
			if (board[x + i][y + j] != BW[i][j]) cnt++;
		}
	}
	return cnt;
}

int main()
{
	string board[50];
	setBoard();

	int n, m, minCnt = 65; //8*8 모두 다시 칠하면 최대 64번
	cin >> n >> m;
	cin.ignore(); //개행문자 무시, 입력 버퍼 비움

	for (int i = 0; i < n; i++) {
		getline(cin, board[i]);
	}

	//차례대로 8칸씩 잘라서 최솟값 비교
	for (int i = 0; i + 8 <= n; i++) {
		for (int j = 0; j+8 <= m; j++) {
			int temp = min(wbCnt(i, j, board), bwCnt(i, j, board));
			if (temp < minCnt) minCnt = temp;
		}
	}
	cout << minCnt;

	return 0;
}

★이번 문제는 정말... 이게 뭐지 싶어서 고민하다가 결국 검색해봤다. 알고 보니까 문제에서 이미 힌트를 많이 줬던 거였다. (문제를 잘 읽자,,,)

1. n m은 주어지는 행렬의 크기임 -> 근데 이제 이걸 무조건 8*8 크기로 만들 거니까 잘라야 됨

2. 문제에서 이미 말하고 있는 거: 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. -> 이 정답 체스판 2가지를 전역변수로 하여 미리 초기화 세팅 시켜놓고 비교하는 형식으로 구현하면 된다.

3. 행렬은 char이나 string둘 다 되는데 string이 더 간편하니 그걸로 하였다. -> string은 한 줄씩 입력받아야 하므로 처음 크기를 입력받고 나서의 개행문자(\n)를 지워줘야 한다. 그래야 그다음 getline(cin, 저장변수)를 쓸 수 있다.
따라서 cin.ignore();을 쓰자. 안 그러면 실행 시 오류 난다.

4. 브루트포스 문제답게 그냥 전부 다 비교한다. 8칸씩 아무거나 잘라도 되는데 최솟값!! 을 찾아야 하므로, for문에서 i+8<=n; 식으로 왼쪽부터 8칸 해서 색칠할 칸 세고, 그다음 칸부터 8칸 해서 색칠할 칸 세고,,, 이런 식으로 크게 반복하면서 세부적으로는 흰색시작이 더 적은 지 검은색시작이 더 적은 지 min함수로 비교하여 최솟값을 저장하는 형식이다.

5. wbCnt, bwCnt같이 세부적으로 계산하는 함수 부분은, 8칸씩 정해져 있으므로 그만큼 반복하며 정답과 비교하고 다른 칸을 카운트한다. 이때 함수에 인자로 시작점을 전달해 주어야 거기서부터 8칸까지 계산할 수 있다.

▣참고: https://cryptosalamander.tistory.com/13

 

---

1436) 영화감독 숌

→https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

#include <iostream>
using namespace std;

int main(){
	int n, cnt=0, title=665;
	cin >> n;

	while (cnt != n) {
		title++;
		int temp = title;

		while (temp != 0) {
			if (temp % 1000 == 666) {
				cnt++;
				break;
			}
			else {
				temp /= 10;
			}
		}
	}
	cout << title;

	return 0;
}

★아니 왜 여기 문제들은 하나같이 다 문제부터 이해가 안 되지,,, 실버 하위단계인데 벌써 큰일 났다 ㄷㄷ
그래도 해설 보면 이해 가서 다행임 (나중엔 해설 봐도 이해 안 될 듯)

아무튼 이번 문제는 666을 첫 번째로 하여 최소 6이 3번 연속 들어가는 종말의 수의 n번째를 구하는 문제이다.
처음엔 이해가 안 가서 5666 다음엔 6666, 7666 이런 식인 줄... 
풀이를 보니 순서가 
666 -> 1666 -> 2666... -> 5666 -> 6660 -> 6661 -> 6662 -> 6663... -> 6666... -> 6669 ->7666
이렇게 되는 거였다. 그냥 6이 3번 연속을 기준으로 하여 제일 작게 나오는 수를 구하는 거니까 5666 다음에는 6660이 오면 된다. (5660 이러면 최소 3개 룰이 깨지니까)

풀이는 다음과 같이 된다.
일단 첫 번째 제목이 666이니까 665로 초기화시키고 1씩 증가하는 루프를 실행한다.
제목이 666, 667, 668... 이런 식으로 증가하면서 그때마다 또 while문으로 0이 아닐 때까지 10으로 나누어서 (일의 자리 지우는 과정) 숫자 끝이 666으로 끝나는지 확인한다. 맞으면 카운트를 증가시키고 첫 번째 while문으로 돌아간다. 이때 break문을 안 넣으면, 66666인 경우 오른쪽부터 3개씩 총 3번 카운트가 더 증가할 것이다. 따라서 한번 찾으면 break를 걸고 다음 숫자로 넘어가야 한다.

마찬가지로 한번 찾았다고 끝나는 게 아니다. 
187번째인 66666을 찾고 싶은 건데, 처음 666이 나올 때 한번 찾았다고 해서 바깥쪽 whlie문까지 종료시켜 버리면 666이 출력될 것이다. 따라서 한번 찾으면 카운트만 증가시키고, 바깥 while문으로 하여 카운트가 n에 도달할 때까지 반복하여 찾아야 된다.

▣참고: https://cocoon1787.tistory.com/155
▣참고: https://cryptosalamander.tistory.com/43

 

---

2839) 설탕 배달 

→https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

#include <iostream>
using namespace std;

int main(){
	int n, res=0;
	cin >> n;

	while (n >= 0) {
		if (n % 5 == 0) {
			res += n / 5;
			cout << res;
			return 0;
		}
		n -= 3;
		res++;
	}
	cout << -1;

	return 0;
}

★이번 문제는 봉지 개수의 최솟값을 구하는 문제로, 최대한 5kg짜리 봉지를 많이 활용하는 것이 좋다. 
따라서 전체적인 while문으로 총 무게 n이 0 미만이 될 때까지 반복하면서 if문으로 5로 나누어 떨어지는지 확인한다. 만약 나누어 떨어진다면, 그 몫만큼을 개수 res로 세고 출력하여 종료한다.
나누어 떨어지지 않는다면 무게 n에서 3kg만큼 빼고 해당 봉지 개수를 res로 증가시킨다.
이 과정을 반복하면서 만약 종료되지 않고 while문을 벗어나면 정확히 나눌 수 없다는 의미이므로 -1을 출력한다.

▣참고: https://codegarden-farmjun.tistory.com/10

 

 

수학을 건너 뛰고 풀어서 그런가 생각보다 잘 안 풀렸다... 반은 문제부터 이해 안 가고 반은 풀이가 감이 안 옴

계속 풀이 찾아보니까 이게 맞나 싶어서 그냥 포기할까도 생각했는데,,, 또 생각해 보니?? 어차피 옛날부터 문제집 풀 때마다 항상 옆에 정답지 펼쳐놓고 모르면 바로 보면서 해설로 공부했었음 맞네 ㅇㅋ

남들은 1시간 아님 하루정도(...) 최대한 혼자 고민해 보라고 하지만,,, 난 그렇게 하다가는 질려서 그냥 때려칠거 같음(몇 주동안 고민하면서 푸는 건 학교 과제로 이미 질리게 하고 있어서 ㄱㅊ,,,)

그래서 백준 문제는 한 몇 십분 생각해도 모르겠으면 그냥 바로 찾아서 풀이를 공부하는 게 더 효과적인 거 같다

일단 브루트포스 문제들은 이제 대충 어떤 식으로 푸는지 알겠음

12단계 끝~!~!!