백준 2503번 : 숫자 야구 - 브루트포스 완전 탐색

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

1.문제설명

이 문제의 답을 구하는 방법은 크게 두가지가 있습니다.

 

첫번째는

123~987중에서 조건이 주어질 때마다 정답이 될 수 있는 후보만 남겨주는 것입니다.

 

두번째는

조건에 부합하는 숫자의 집합을 구해서 모든 조건의 교집합을 구해내는 것입니다.

 

첫번째로 구하는게 123~987 내에서 계산하는 숫자를 계속 좁혀나가니까 효율적입니다.

저는 처음에 든생각이 두번째로 푸는거라 이악물고 풀었는데 답이 나오네요

테스트케이스가 워낙 작아서 두번째도 가능합니다.

 

두가지방법 모두 코드를 올립니다.

 

 

---

 

2.문제풀이코드 C++

첫번째 방법

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[1000];

void compare(int x, int y, int z) {

	for (int i = 123; i <= 987; i++) {
		if (ch[i]) {
			int s = 0, b = 0;

			int arr1[3] = { i / 100, (i % 100) / 10 ,i % 10 };
			int arr2[3] = { x / 100, (x % 100) / 10 ,x % 10 };


			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if(j==k && (arr1[j]==arr2[k])){
						s++;
					}
					else if (j != k && arr1[j] == arr2[k]) {
						b++;
					}
				}
			}

			//후보에서 제외
			if (!(y == s && z == b)) {
				ch[i] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	//ch배열 초기화 
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			for (int k = 1; k <= 9; k++) {
				if (i != j && k != j && i != k) {
					ch[i * 100 + 10 * j + k] = 1;
				}
			}
		}
	}


	for (int i = 0; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		compare(x, y, z);
	}


	int ans = 0;
	for (int i = 0; i < 1000; i++) {
		if (ch[i]) ans++;
	}

	cout << ans << '\n';

	return 0;
}

 

두번째 방법

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[101][1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, s, b;
		cin >> a >> s >> b;

		int x = a / 100;
		int y = (a % 100) / 10;
		int z = a % 10;

		if (s == 3 && b == 0) {
			cout << 1 << '\n';
			return 0;
		}
		else if (s == 0 && b == 3) {
			ch[i][z * 100 + x * 10 + y] = 1;
			ch[i][y * 100 + z * 10 + x] = 1;
		}
		else if (s == 1 && b == 2) {
			ch[i][100 * x + 10 * z + y] = 1;
			ch[i][100 * z + 10 * y + x] = 1;
			ch[i][100 * y + 10 * x + z] = 1;
		}
		else if (s == 2 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * x + 10 * y + j] = 1;
					ch[i][100 * x + 10 * j + z] = 1;
					ch[i][100 * j + 10 * y + z] = 1;
				}
			}
		}
		else if (s == 1 && b == 1) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * x + 10 * j + y] = 1;
					ch[i][100 * x + 10 * z + j] = 1;
					ch[i][100 * z + 10 * y + j] = 1;
					ch[i][100 * j + 10 * y + x] = 1;
					ch[i][100 * j + 10 * x + z] = 1;
					ch[i][100 * y + 10 * j + z] = 1;
				}
			}
		}
		else if (s == 0 && b == 2) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * j + 10 * x + y] = 1;
					ch[i][100 * y + 10 * x + j] = 1;
					ch[i][100 * y + 10 * j + x] = 1;
					ch[i][100 * z + 10 * j + x] = 1;
					ch[i][100 * z + 10 * x + j] = 1;
					ch[i][100 * j + 10 * z + x] = 1;
					ch[i][100 * z + 10 * j + y] = 1;
					ch[i][100 * y + 10 * z + j] = 1;
					ch[i][100 * j + 10 * z + y] = 1;
				}
			}
		}
		else if (s == 1 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					if (j != z && j != x && j != y && j != k && k != x && k != y && k != z) {
						ch[i][100 * x + 10 * j + k] = 1;
						ch[i][100 * j + 10 * y + k] = 1;
						ch[i][100 * j + 10 * k + z] = 1;
					}
				}
			}
		}
		else if (s==0 && b == 1) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					if (j != z && j != x && j != y && j != k && k != x && k != y && k != z) {
						ch[i][100 * j + 10 * x + k] = 1;
						ch[i][100 * j + 10 * k + x] = 1;

						ch[i][100 * y + 10 * j + k] = 1;
						ch[i][100 * j + 10 * k + y] = 1;

						ch[i][100 * z + 10 * j + k] = 1;
						ch[i][100 * j + 10 * z + k] = 1;

					}
				}
			}
		}
		else if (s == 0 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					for (int t = 1; t <= 9; t++) {
						if (j != z && j != x && j != y && j != k && k != x && k != y && k != z
							&& x != t && y != t && z != t && k != t && j != t) {
							ch[i][100 * j + 10 * t + k] = 1;
						}
					}
				}
			}

		}
	}

	int ans = 0;

	for (int i = 100; i < 1000; i++) {
		bool flag = true;
		for (int j = 0; j < n; j++) {
			if (ch[j][i] == 0) {
				flag = false;
				break;
			}
		}
		if (flag) ans++;
	}

	cout << ans << '\n';
	return 0;
}

 

백준 2503번 숫자야구