문제 링크: https://www.acmicpc.net/problem/18119

 

비트마스크 활용 문제입니다.

문자열을 마스크로 바꿔서 저장해둔 뒤, 쿼리가 발생할 때마다 모든 문자열과 현재 알고있는 알파벳 마스크를 적당히 연산을 해서 읽을 수 있는지 없는지 확인합니다.

읽을 수 있는지 없는지 체크하는 방법은 (현재 알고 있는 알파벳 마스크 & 단어 마스크) == 단어 마스크 가 되면 됩니다. 적당히 그림을 그려 보면 바로 이해가 되실겁니다.

 

#pragma GCC optimize ("Ofast")

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


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	string s;
	vector<int> words(n);
	for (auto& w : words) {
		cin >> s;
		
		for (auto& c : s) {
			w |= 1 << (c - 'a');
		}
	}

	int brain = 0x3ffffff;

	int q;
	char ch;
	while (m--) {
		cin >> q >> ch;
		
		if (q == 1) {
			// forget
			brain &= ~(1 << (ch - 'a'));
		}
		else {
			// remember
			brain |= 1 << (ch - 'a');
		}


		int readable = 0;
		for (auto& w : words) {
			if ((brain & w) == w)
				++readable;
		}
		cout << readable << '\n';
	}


	return 0;
}

사실 문제를 대충 읽고 모음 관련 처리를 안했는데 통과가 됩니다.

'모음은 완벽하게 외웠기 때문에 절대 잊지 않는다'라는 것이 입력으로 자음이 절대 안들어온다는 의미같습니다. 게시판에 보니 그런 느낌의 답변이 있네요.

반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 1043: 거짓말  (0) 2020.06.29
[백준][C++] 1036: 36진수  (0) 2020.06.24
[백준][C++] 17081: RPG Extreme  (2) 2020.06.16
[백준][C++] 18111: 마인크래프트  (0) 2020.06.15
[백준][C++] 2293: 동전 1  (0) 2020.06.14