이번에는 백준 1062번 가르침 문제를 풀어보았습니다.
처음에는 알파벳 26개 중에서 K개를 선택하는 모든 경우를 탐색하면 된다고 생각했습니다.
하지만 문제를 다시 읽어보니 모든 단어는 "anta"로 시작하고 "tica"로 끝난다는 조건이 있었습니다.
즉, a, n, t, i, c는 반드시 배워야 하는 알파벳이므로 이 다섯 글자를 미리 선택한 상태에서 나머지 알파벳만 조합으로 선택하도록 구현하였습니다.
또한 단어는 비트마스킹으로 저장하여 비트 연산만으로 읽을 수 있는 단어인지 확인하도록 구현하였습니다.
문제 설명
학생들은 배운 알파벳으로만 이루어진 단어를 읽을 수 있습니다.
총 K개의 알파벳을 가르칠 수 있으며, 읽을 수 있는 단어의 개수를 최대로 만들어야 합니다.
최대로 읽을 수 있는 단어의 개수를 구하는 문제입니다.
풀이 아이디어
각 단어를 비트마스킹을 이용하여 하나의 정수로 저장하였습니다.
또한 모든 단어는 "anta"로 시작하고 "tica"로 끝나므로 a, n, t, i, c는 반드시 배워야 합니다.
따라서 처음부터 다섯 개의 알파벳을 배운 상태로 시작하였습니다.
이후 남은 알파벳들 중에서 K-5개를 조합으로 선택하였습니다.
조합이 완성되면 비트 연산을 이용하여 현재 배운 알파벳으로 읽을 수 있는 단어의 개수를 계산하고 최댓값을 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,K;
int inp_arr[26];
int ret = 0;
int learned_setting(int num){
num |= (1 << ('a'-'a'));
num |= (1 << ('n'-'a'));
num |= (1 << ('t'-'a'));
num |= (1 << ('i'-'a'));
num |= (1 << ('c'-'a'));
return num;
}
void solve(int learned){
int tmp = 0;
for (int i=0; i<N; i++) {
if ((learned & inp_arr[i]) == inp_arr[i])
tmp++;
}
ret = max(ret, tmp);
}
void combi(int learned, int cnt, int n) {
if (cnt == K) {
solve(learned);
return;
}
for (int i=n; i<26; i++) {
if (learned & (1 << i)) continue;
combi(learned | (1 << i), cnt+1, i+1);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> K;
for (int i=0; i<N; i++) {
string s;
cin >> s;
for (int j=0; j<s.length(); j++) {
inp_arr[i] |= (1 << (int)(s[j] - 'a'));
}
}
if (K < 5) {
cout << 0 << '\n';
return 0;
}
int learned = learned_setting(0);
combi(learned,5,0);
cout << ret << '\n';
return 0;
}풀이 흐름
- 입력받은 단어를 비트마스킹으로 저장합니다.
a,n,t,i,c를 미리 배운 상태로 설정합니다.- K가 5보다 작은 경우 바로 0을 출력합니다.
- 나머지 알파벳을 조합으로 선택합니다.
- 조합이 완성되면 현재 알파벳으로 읽을 수 있는 단어의 개수를 계산합니다.
- 최댓값을 갱신합니다.
- 모든 조합을 탐색한 뒤 결과를 출력합니다.
구현 포인트
1. 단어를 비트마스킹으로 저장
각 단어를 하나의 정수로 저장하였습니다.
inp_arr[i] |= (1 << (int)(s[j] - 'a'));예를 들어
abc라면
0111처럼 저장됩니다.
비트 연산만으로 포함 여부를 확인할 수 있도록 구현하였습니다.
2. 반드시 배워야 하는 알파벳 설정
모든 단어는 "anta"로 시작하고 "tica"로 끝납니다.
따라서 a, n, t, i, c는 반드시 배워야 합니다.
int learned_setting(int num){
num |= (1 << ('a'-'a'));
num |= (1 << ('n'-'a'));
num |= (1 << ('t'-'a'));
num |= (1 << ('i'-'a'));
num |= (1 << ('c'-'a'));
return num;
}조합 역시 다섯 글자를 이미 선택한 상태에서 시작하였습니다.
int learned = learned_setting(0);
combi(learned, 5, 0);3. K가 5보다 작은 경우
필수 알파벳 다섯 개도 배우지 못하는 경우에는 어떤 단어도 읽을 수 없습니다.
if (K < 5) {
cout << 0 << '\n';
return 0;
}따라서 바로 0을 출력하도록 하였습니다.
4. 조합 생성
필수 알파벳을 제외한 나머지 알파벳을 조합으로 선택하였습니다.
for (int i=n; i<26; i++) {
if (learned & (1 << i)) continue;
combi(learned | (1 << i), cnt+1, i+1);
}이미 배운 알파벳은 다시 선택하지 않도록 처리하였습니다.
5. 비트 연산으로 읽을 수 있는 단어 확인
현재 배운 알파벳으로 단어를 읽을 수 있는지 비트 연산으로 확인하였습니다.
if ((learned & inp_arr[i]) == inp_arr[i])
tmp++;예를 들어
단어 : abc -> 0111
배운 문자 : abcd -> 1111이라면
0111 & 1111 = 0111이 되어 단어를 읽을 수 있다는 것을 확인할 수 있습니다.
모든 단어를 확인한 뒤 최댓값을 갱신하였습니다.
ret = max(ret, tmp);