c/c++ 백준_1342 행운의 문자열

알고리즘은 간단했다. 단순히 완전 탐색 방식으로 조합의 모든 경우를 계산하고 중복되는 만큼 ex) aabab와 같은 경우 3! 2!으로 나눠주면 됐다.

문자열보단 조합론(?)에 가까운 문제였다. 하지만 조합은 1 3 2 처럼 모두 다른 숫자나 문자로 구성되었지만 이 문제는 중복된 문자들도 있기 때문에 각 문자마다 id값을 주어 구분하였다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<pair<int, char>> v;// id, 문자
int over[27];
int visited[27];
string s;
int n;
char ans[11];
int res = 0;

int factorial(int n) {

	long long sum = 1;
	for (int i = 1; i <= n; ++i) {
		sum = sum * i;
	}
	return sum;
}
void com(int x) {
	if (x == s.size()) {
		for (int i = 0; i < x-1; ++i) {
			if (ans[i] == ans[i + 1]) {
				return ;
			}
		}
		res++;
	}

	for (int i = 0; i < s.size(); ++i) {
		if (!visited[v[i].first]) {
			visited[v[i].first] = 1;
			ans[x] = (v[i].second);
			com(x + 1);
			visited[v[i].first] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> s;
	for (int i = 0; i < s.size(); ++i) {
		
		over[s[i] - 'a']++;
		v.push_back({ i,s[i] });
	}

	com(0);
	int value = 1;

	for (int i = 0; i < 26; ++i) {
		if(over[i])
			value *= factorial(over[i]);
	}
	int answer = res / value;
	cout << answer;

}

그 외에는 N과M 문제와 비슷한 것 같다.