가르침

분석

a, b, c 있을 때 해당 문자를 배웠냐 안배웠냐를 따지는거임.

"abc", "bac" 이런거 순서에 상관없이 체크만 하면된다. => "조합"이다. (비트마스킹을 통한)

abc를 배우면 7이라고치자
(a = 1, b = 2, c = 4)

그리고 bc, ab라는 단어가 왔을 때 읽을 수 있느냐 없느냐는 & 연산자로 통해서 구현할 수 있다.

후기

개어려워서 못 풀었다.

조합인것도 알았고 비트마스킹으로 구현해야 한다는 것도 알았다(재귀로 구현할 수 있지만 비효율적임)

근데도 못 풀었는데 그 이유가

char b[4] = { 'a', 'b', 'c', 'd' };
int b1[4];
b1[0] = 1;
for (int i = 0; i < (1 << 4); ++i)
{
	int cnt = 0;
	string s2;
	for (int j = 0; j < 4; ++j)
	{
		if (i & (1 << j))
		{
			cout << b[j] << " ";
		}
	}
	cout << endl;
}
// 출력
a
b
a b
c
a c
b c
a b c
d
a d
b d
a b d
c d
a c d
b c d
a b c d

위와같이 아주 잘 나온다.

여기서 i & 1 << j에 걸리는 경우 count를 증가시켜서 입력받은 k와 일치하면 출력할려고했음.

그러다보니까 프로그램 실행하는 시간이 엄청걸림.(모든 경우의 수를 다 따지다 보니까)

배운 단어의 수를 2개라 했을 때 26개의 알파벳중에서 모든 경우의 2개를 다 뽑아서 입력받은 문자열에다가 대입해서 몇개를 최대로 읽을 수 있는지 봐야하니까.

그러니까 배운 단어의 수가 4개 이하려면 무조건 0임. atna + tica 는 들어가야하니까.

cpp