[BOJ 15811 // C++] 복면산?!

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15811번 문제인 복면산?!이다.
문제는 아래 링크를 확인하자.

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

15811번: 복면산?!

주어지는 각 문자를 미지수 하나로 대응하고 수식으로 바꾸면, 각 미지수에 서로 다른 한자리 정수를 집어넣어 보는 완전탐색을 통해 문제를 해결할 수 있다.

 

등장하는 문자의 가짓수는 10개를 넘을 수 있음에 유의하여 구현하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int idx = 1;
int chartoidx[128];
ll cnt[27];
ll val = 0;
bool ans = 0;
bool visited[10];

void func(int cur) {
	if (cur == idx) {
		if (val == 0) ans = 1;
		return;
	}
	for (int i = 0; i < 10; i++) {
		if (visited[i]) continue;
		visited[i] = 1;
		val += cnt[cur] * i;
		func(cur + 1);
		val -= cnt[cur] * i;
		visited[i] = 0;
	}
}

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

	string s1, s2, s3; cin >> s1 >> s2 >> s3;
	int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
	ll digit = 1;
	for (int i = s1len - 1; i > -1; i--) {
		if (chartoidx[s1[i]] == 0) chartoidx[s1[i]] = idx++;
		cnt[chartoidx[s1[i]]] += digit;
		digit *= 10;
	}
	digit = 1;
	for (int i = s2len - 1; i > -1; i--) {
		if (chartoidx[s2[i]] == 0) chartoidx[s2[i]] = idx++;
		cnt[chartoidx[s2[i]]] += digit;
		digit *= 10;
	}
	digit = 1;
	for (int i = s3len - 1; i > -1; i--) {
		if (chartoidx[s3[i]] == 0) chartoidx[s3[i]] = idx++;
		cnt[chartoidx[s3[i]]] -= digit;
		digit *= 10;
	}

	if (idx > 11) {
		cout << "NO";
		return 0;
	}

	func(1);

	if (ans) cout << "YES";
	else cout << "NO";
}