백준 단계 12 : 브루트 포스 (C++)

https://shine-slowly.tistory.com/35

알고리즘 : 브루트 포스란

브루트 포스에 대한 개념이 아예 없다면 위 포스팅을 간단하게 읽고 오는 것을 추천한다.

 

 

2798. 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n, m, max = 0;
	cin >> n >> m;
	vector <int> card(n);
	for (int i = 0; i < n; i++)
	{
		cin >> card[i];
	}
	for (int i = 0; i < n - 2; i++)
	{
		for (int j = i + 1; j < n - 1; j++)
		{
			for (int k = j + 1; k < n; k++)
			{
				if ((max < card[i] + card[j] + card[k]) && (card[i] + card[j] + card[k] <= m))
					max = card[i] + card[j] + card[k];
			}
		}
	}

	cout << max;
}

삼중 for문으로 구현해야하는 코드이다. 삼중 for문이 아닌 다른 방식이 있다면 그 방식을 사용하는 것이 좋겠지만 단계가 브루트 포스라서 이게 가장 간결한 코드일 것이다.

 

 

 

2231. 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

#include<iostream>
#include<string>
using namespace std;
int main() {
	int n, sum, flag = 0;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		string temp = to_string(i);
		sum = i;
		for (int j = 0; j < temp.length(); j++)
		{
			sum += temp[j] - '0';
		}
		if (sum == n) {
			cout << i;
			flag = 1;
			break;
		}
	}
	if (flag == 0) {
		cout << flag;
	}
	return 0;
}

생성자는 n보다 클 수 없으니까 for문으로 1부터 n-1까지 생성자인지 확인하는 코드를 작성하였다. 나는 string으로 변환해서 접근하는 방식을 했는데.아래와 같이 작성해도 된다.

int num = i;
while (num!= 0) {
	sum += num % 10;
	num /= 10;
}

숫자의 각 자리수를 더해야하거나 뽑아야할 때 보통 사용하는 방식이다. 이러한 방식으로 대체해도 된다.

 

 

 

19532. 수현이는 4차 산업혁명 시대에 살고 있는 중학생이다. 코로나 19로 인해, 수현이는 버추얼 학교로 버추얼 출석해 버추얼 강의를 듣고 있다. 수현이의 버추얼 선생님은 문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다.

#include<iostream>
using namespace std;
int main() {
	int a, b, c, d, e, f;
	int x, y;
	cin >> a >> b >> c >> d >> e >> f;
	if (a == 0) {
		y = c / b;
		x = (f - e * y) / d;
	}
	else if (d == 0) {
		y = f / e;
		x = (c - b * y) / a;
	}
	else {
		y = (d * c - a * f) / (b * d - a * e);
		x = (c - b * y) / a;
	}
	
	cout << x << " " << y;
	return 0;
}

-999부터 999까지 하나씩 대입하면서 해도 시간제한에 걸리지 않는다.

 

 

 

1018. 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n, m, repaint, min = 64;
	cin >> n >> m;
	// vector <vector<char>> board(n, vector<char>(m));
	vector <string> board(n);
	for (int i = 0; i < n; i++)
	{
		cin >> board[i];
	}

	vector <string> temp = board;
	for (int i = 0; i <= n - 8; i++)
	{
		for (int j = 0; j <= m - 8; j++)
		{
			repaint = 0;
			for (int k = 0; k < 8; k++)
			{
				for (int l = 0; l < 7; l++)
				{
					if (k >= 1 && l == 0) {
						if (board[i + k - 1][j + l] == board[i + k][j + l]) {
							if (board[i + k][j + l] == 'W')
								board[i + k][j + l] = 'B';
							else
								board[i + k][j + l] = 'W';

							repaint++;
						}
					}

					if (board[i + k][j + l] == board[i + k][j + l + 1]) {
						if (board[i + k][j + l + 1] == 'W')
							board[i + k][j + l + 1] = 'B';
						else
							board[i + k][j + l + 1] = 'W';

						repaint++;
					}
				}
			}
			if (min > repaint)
				min = repaint;

			board = temp;

			repaint = 1;
			if (board[i][j] == 'W')
				board[i][j] = 'B';
			else
				board[i][j] = 'W';

			for (int k = 0; k < 8; k++)
			{
				for (int l = 0; l < 7; l++)
				{
					if (k >= 1 && l == 0) {
						if (board[i + k - 1][j + l] == board[i + k][j + l]) {
							if (board[i + k][j + l] == 'W')
								board[i + k][j + l] = 'B';
							else
								board[i + k][j + l] = 'W';

							repaint++;
						}
					}

					if (board[i + k][j + l] == board[i + k][j + l + 1]) {
						if (board[i + k][j + l + 1] == 'W')
							board[i + k][j + l + 1] = 'B';
						else
							board[i + k][j + l + 1] = 'W';

						repaint++;
					}
				}
			}
			if (min > repaint)
				min = repaint;

			board = temp;
		}
	}

	cout << min;
}

내가 기존에 작성했던 코드이다. 하나씩 비교해가면서 값을 바꾸는 것이다. 

시간은 이정도가 나온다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <string> whiteBoard{
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW"
};
vector <string> blackBoard{
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB"
};

int white_start(int x, int y, vector<string> board) {
	int cnt = 0;
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (board[x + i][y + j] != whiteBoard[i][j])
				cnt++;
		}

	}
	return cnt;
}

int black_start(int x, int y, vector<string> board) {
	int cnt = 0;
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (board[x + i][y + j] != blackBoard[i][j])
				cnt++;
		}

	}
	return cnt;
}


int main() {
	int n, m, repaint, minVal = 64;
	cin >> n >> m;
	vector<string>board(n);
	for (int i = 0; i < n; i++)
	{
		cin >> board[i];
	}

	for (int i = 0; i <= n - 8; i++)
	{
		for (int j = 0; j <= m - 8; j++)
		{
			int temp = min(white_start(i, j, board), black_start(i, j, board));
			if (minVal > temp)
				minVal = temp;
		}
	}

	cout << minVal;
}

보편적으로 찾아볼 수 있는 코드이다. 가장 직관적인 코드라고 생각한다.

시간은 이정도 나온다.

 

 

 

1436. 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.

#include<iostream>
using namespace std;
int main() {
	int n, cnt = 0;
	cin >> n;
	int temp, ans = 665;
	while (cnt != n)
	{
		ans++;
		temp = ans;
		while (temp != 0)
		{
			if (temp % 1000 == 666) {
				cnt++;
				break;
			}
			else
				temp /= 10;
		}
	}
	cout << ans;
}

다른 티스토리를 참고하여 작성하였다. 1씩 증가해가며 그 숫자 안에 666이 들어있는지 판단하고 들어있으면 cnt를 1 증가시켜 입력값과 동일한지 확인하는 것이다.

1000으로 나눈 나머지가 666이 된다는 것은, 천자리 미만 값이 666으로 이루어져 있다는 뜻이다. 즉, 뒤에 하나씩 빼면서 666이 맨 마지막 세숫자로 오는지 확인을 하고 그런 경우에 cnt를 증가시키는 코드이다.

https://cocoon1787.tistory.com/155

[C/C++] 백준 1436번 - 영화감독 숌 (브루트 포스)

참고한 코드이다.

 

 

 

2839. 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int big = (n / 5) + 1;
	int small = 0;
	while (big--) {
		if ((n - big * 5) % 3 == 0) {
			small = (n - big * 5) / 3;
			break;
		}
	}
	cout << big + small;
}

Greedy Algorithm 문제라고 한다. DP로도 풀 수 있다고 하는데 아직 무슨 알고리즘인지 잘 모르니 일단은 그리디 알고리즘에 대해서만 아주 짧게 알아보도록 하겠다. 그리디 알고리즘의 자세한 부분이나 DP는 나중에 알고리즘에서 다룰 것이다.

 

Greedy Algorithm (그리디 알고리즘)

현재 상황에서 가장 최적이라고 생각하는 해를 선택하는 방법이다. 앞으로 남은 선택을 고려하지 않으므로 항상 최적의 해를 보장하진 않는다.

파란 경로가 그리디 알고리즘

 

부분 최적해가 모여서 전체 최적해가 될 수 있는 상황에서 그리디 알고리즘을 사용해서 최적해를 구할 수 있다고 한다.

위와 같은 상황에서도 서울-대전의 부분 최적해와 대전-부산의 부분 최적해가 서울-부산의 전체 최적해가 된다.

 

그렇다면 왜 거스름돈 문제는 그리디 알고리즘으로 풀 수 있는 것일까?

동전의 큰 단위가 항상 작은 단위의 배수이기 때문이다. 작은 단위의 동전들을 조합해서 다른 해가 나올 수가 없다.

예를 들어 2300원을 거슬러주기 위한 방법은 500원짜리 4개, 100원짜리 3개가 될 것이다.

하지만 화폐 단위가 500, 400, 100이라고 할 경우 800원을 거슬러주기 위한 가장 좋은 방법은 400원 2개이다. 하지만 위에 작성했던 코드로 계산을 하면 500원 1개와 100원짜리 3개가 출력될 것이다. 

 

https://it-eldorado.tistory.com/53

그리디 알고리즘 (Greedy Algorithm) 정당성 증명 방법

https://www.itsmo.dev/greedy-algorithm/

[Algorithm] Greedy Algorithm (그리디 알고리즘, 탐욕법) | itsmo.dev