9480. 민정이와 광직이의 알파벳 공부

LEVEL D3

 

단어를 합쳐서 모든 알파벳이 (a~z까지) 1개 이상 존재하는 조합을 찾는 문제이다.

 

가지고 있는 모든 단어의 조합을 구하여 문제를 해결하였다.

 

a = 0x01 . b = 0x02, c = 0x04로 초기화를 한 후에 단어에 맞게 비트연산을 하여 구했다.

 

abc인 경우 0x07을 가지게 되며 0000 0111로 표현된다. 

 

abc 와 fa를 더 할 경우 da(0x05) 는 0000 1111로 표현 되기 때문에 현재 a,b,c,d를 가지고 있다고 생각하고 풀었다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXAdrmW61ssDFAXq&categoryId=AXAdrmW61ssDFAXq&categoryType=CODE

SW Expert Academy

 

소스보기

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
int T, N;
const int correct = 0x3ffffff;
int map[26];
int word[15];
int answer;
void initMap() 
{
	for (int i = 0; i < 26; i++) {
		map[i] = 0x01 << i;
	}
}
void solution(int begin, int curWord) 
{
	if (curWord == correct) {
		answer += 1;
		//return;
	}
	for (int i = begin; i < N; i++) {
		solution(i + 1, curWord | word[i]);
	}
}
int main()
{
	initMap();
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d", &N);
		string str;
		for (int i = 0; i < N; i++) {
			cin >> str;
			int n = 0;
			for (int j = 0; j < str.length(); j++) {
				n |= map[str[j] - 'a'];
			}
			word[i] = n;
		}
		answer = 0;
		solution(0, 0);
		printf("#%d %d\n",tc, answer);
	}
}