코드카타 문제
오늘의 코드카타 문제는 백준에 있었던 문제인 가르침(1062번)이다.
문제를 요약하자면, 알파벳 26개 중 K개만 배워서 최대한 많은 단어를 읽을 수 있도록 하는 것이었다.
조건은 다음과 같다.
- 모든 단어는 "anta"로 시작해서 "tica"로 끝난다. 그래서
a, n, t, i, c5개 문자는 모든 단어에 공통으로 등장한다. - 배울 수 있는 문자는 정확히 K개이고, 이 5개 문자를 배우지 않으면 어떤 단어도 읽을 수 없다.
- 한 단어를 이루는 문자들이 전부 배운 문자에 포함될 때만 그 단어를 읽을 수 있다.
K가 5보다 작으면 애초에 필수 문자조차 다 못 배우므로 0을 출력한다.
문제를 보자마자 제약 조건부터 확인했다.
- 단어 개수 N ≤ 50, 배울 수 있는 문자 개수 K ≤ 26.
여기서 핵심은 다음과 같았다.
- a, n, t, i, c는 무조건 배운다. 모든 단어에 공통으로 들어있는 문자이므로 배우지 않을 이유가 없다. 이 5개를 먼저 고정해두면 문제가 "나머지 문자 중 몇 개를 더 배울지"로 단순해진다.
- 나머지는 21개 문자 중 K-5개를 고르는 조합 문제로 줄어든다. 26개에서 고정된 5개를 빼면 21개가 남고, 여기서 K-5개를 고르는 조합은 아무리 많아도
C(21, 10)~C(21, 11)근방인 수십만 가지 수준이라 완전 탐색이 가능하다. 이 조합을 DFS로 만들었다. - 각 조합이 몇 단어를 커버하는지는 비트 연산 한 줄로 판정된다. 단어의 문자 집합을 비트마스크로 만들어 두면,
(word & bits) == word인지만 확인해도 그 단어가 배운 문자만으로 이루어져 있는지 바로 알 수 있다.
상태 공간이 크지 않으니 복잡한 최적화 없이 가능한 모든 문자 조합을 만들고, 각 조합에서 읽을 수 있는 단어 수를 세어 최댓값을 갱신하는 완전 탐색으로 충분하다고 판단했다.
그래서 풀이를 세 부분으로 나눴다.
- 전처리: 각 단어를 문자 집합의 비트마스크로 바꾸고, 예외 케이스(K<5, K=26)를 먼저 처리한다.
- 조합 생성: a, n, t, i, c를 고정한 뒤, 나머지 21개 문자 중 K-5개를 고르는 조합을 DFS로 만든다.
- 최댓값 갱신: 조합이 완성될 때마다 몇 개의 단어를 읽을 수 있는지 세어서 최댓값을 갱신한다.
1. 전처리
각 단어를 한 글자씩 확인하면서, 그 글자에 해당하는 비트가 아직 안 켜져 있으면 켜준다. 이렇게 하면 중복된 글자가 있어도 "이 단어에 어떤 문자들이 쓰였는가"를 비트마스크 하나로 표현할 수 있다.
int a = 0;
for (char c : s)
{
// 이미 체크한 단어는 비트를 올리지 말 것
if ((a & (1 << (c - 'a'))) == 0)
{
a += (1 << (c - 'a'));
}
}
arr[i] = a;이렇게 만든 arr[i]는 이후 어떤 문자 조합으로 그 단어를 읽을 수 있는지 판정하는 데 그대로 쓰인다.
이어서 두 가지 예외를 먼저 처리한다. K가 5보다 작으면 a, n, t, i, c조차 다 배울 수 없으니 0을 출력하고, K가 26이면 알파벳을 전부 배우는 것이니 모든 단어를 읽을 수 있어 바로 N을 출력한다.
if (k < 5)
{
cout << 0 << "\n";
return 0;
}
else if (k == 26)
{
cout << n << "\n";
return 0;
}2. 조합 생성
a, n, t, i, c는 모든 단어에 등장하므로 배우지 않을 이유가 없다. 그래서 이 5개 비트를 먼저 켜둔 bits를 만들고, DFS는 여기에 없는 비트만 골라서 나머지 K-5개를 채우도록 짰다.
int bits = 0;
bits += (1 << ('a' - 'a'));
bits += (1 << ('n' - 'a'));
bits += (1 << ('t' - 'a'));
bits += (1 << ('i' - 'a'));
bits += (1 << ('c' - 'a'));
dfs(0, 0, bits);DFS 내부에서는 index부터 25까지 훑으면서 아직 켜지지 않은 비트만 골라 다음 재귀로 넘어간다. index를 하나씩 밀어가며 진행하기 때문에 같은 조합이 중복해서 만들어지지 않는다.
for (int i = index; i < 26; ++i)
{
if ((bits & (1 << i)) == 0)
{
dfs(i + 1, cnt + 1, bits | (1 << i));
}
}cnt가 k - 5에 도달하면, 그 시점의 bits가 곧 "이번에 배우기로 한 K개 문자 조합" 하나를 의미한다.
3. 최댓값 갱신
조합이 완성되면(cnt == k - 5), 모든 단어를 돌면서 그 단어의 비트마스크가 지금 조합(bits)에 완전히 포함되는지 확인한다. (num & bits) == num이 참이면 단어를 이루는 문자가 전부 배운 문자 안에 있다는 뜻이므로 읽을 수 있는 단어다.
if (cnt == k - 5)
{
int temp_val = 0;
for (int num : arr)
{
// 이 단어는 통과한 것이므로 1을 증가
if ((num & bits) == num)
{
temp_val++;
}
}
// 각 조합마다 테스트해보면서 더 많은 단어를 배울 때까지 최댓값 갱신
if (max_val < temp_val)
{
max_val = temp_val;
}
return;
}이렇게 센 temp_val이 지금까지의 max_val보다 크면 갱신한다. DFS가 가능한 모든 조합을 다 만들 때까지 이 과정을 반복하므로, 마지막에 남는 max_val이 곧 K개의 문자로 읽을 수 있는 단어의 최댓값이 된다. 참고로 max_val은 전역 변수라 처음부터 0으로 초기화되어 있고, 조합은 최소 한 번 이상 반드시 만들어지기 때문에 게리맨더링 문제처럼 "갱신이 하나도 안 됐을 때"를 따로 걸러줄 필요는 없었다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, max_val;
vector<int> arr;
void dfs(int index, int cnt, int bits)
{
// 최종 횟수에 다다를 때
if (cnt == k - 5)
{
// 해당 조합에서 단어와 일치한다면
int temp_val = 0;
for (int num : arr)
{
// 이 단어는 통과한 것이므로 1을 증가
if ((num & bits) == num)
{
temp_val++;
}
}
// 각 조합마다 테스트해보면서 더 많은 단어를 배울 때까지 최댓값 갱신
if (max_val < temp_val)
{
max_val = temp_val;
}
return;
}
// 이미 없는 비트를 기반으로 하나씩 조합을 수행한다.
for (int i = index; i < 26; ++i)
{
if ((bits & (1 << i)) == 0)
{
dfs(i + 1, cnt + 1, bits | (1 << i));
}
}
}
int main()
{
cin >> n >> k;
arr.assign(n, 0);
for (int i = 0; i < n; ++i)
{
string s;
cin >> s;
int a = 0;
for (char c : s)
{
// 이미 체크한 단어는 비트를 올리지 말 것
if ((a & (1 << (c - 'a'))) == 0)
{
a += (1 << (c - 'a'));
}
}
arr[i] = a;
}
if (k < 5)
{
cout << 0 << "\n";
return 0;
}
else if (k == 26)
{
cout << n << "\n";
return 0;
}
int bits = 0;
bits += (1 << ('a' - 'a'));
bits += (1 << ('n' - 'a'));
bits += (1 << ('t' - 'a'));
bits += (1 << ('i' - 'a'));
bits += (1 << ('c' - 'a'));
dfs(0, 0, bits);
cout << max_val;
return 0;
}