부분수열의 합이 될 수 없는 것
20개의 수열 => 부분수열의 개수는 최대 2의 n승 => 최대 N개의 원소가 있는 부분수열의 원소를 더하는 경우 N => 2의 n승 * n의 경우의 수가 있다. bool exists[1 << 20971520 + 1];
이때 비트마스크가 나타내는 것은 실배열의 위치값이다. 예를 들어 5 2 1 6 이라는 배열이 있고, 비트마스크가 1 0 1 0, 즉 2 + 8 = 10이라면 5와 1을 포함한 부분수열이라는 것을 알 수 있다.
#include <iostream>
using namespace std;
int n;
int S[21];
bool exists[20 * 100000 + 10]; // 부분수열을 비트마스크로 저장, 부분수열의 합이 sum인 부분수열이 있으면 true
// 모든 부분수열을 확인하고 exists에 표시한다.
void solve() {
// 모든 상태를 확인
for (int i = 1; i < (1 << n); i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) // 현재 탐색하고 있는 부분수열에 j번째 원소가 속해있다면
sum += S[j];
}
exists[sum] = true;
}
for (int i = 1;; i++)
if (exists[i] == false) {
cout << i << endl;
break;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> S[i];
solve();
}
어려웠던 것
(1) exists , 즉 부분수열의 합이 될 수 있는 것을 담아두는 배열의 초기 크기설정을 어떻게 해야할지
(2) 모든 부분수열의 상태를 탐색하는 방법
(3) 비트마스크 자체가 의미하는 것 ⇒ 원배열의 ‘위치’를 나타내어 선택하는 것임을 알게 되었다.
(4) 처음으로 합이 될 수 없는 것을 찾아내는 로직 for(int i = 1; ; i++) 다음과 같이 변수를 지정함과 동시에 while과 유사하게 사용할 수 있다.
단어 개수가 최대가 되도록 K개의 글자를 뽑는다. 모든 부분수열에 대해서 (수열은 모든 단어) 뽑은 글자에 대해, 읽을 수 있는 단어의 개수를 계산한다. 이때 이 부분수열의 원소의 수는 항상 K개이다. 시간 복잡도는 최대 2^15 * 50 = 1,638,400이다.
아니다. 26개의 모든 영어 중에서 뽑는거다. 아니다. 문자열로 주어진 문자들 중에서만 뽑는거다.
모르겠는 것 : 문자들 중에서 K개만 뽑는 비트마스크를 만드는 것 그리고 또 ? 어디서 부분수열의 집합을 만들어야하는지 모르겠다. => 문자열에 나오는 문자들만으로 이루어진 배열을 만들어 거기에서 비트마스크를 사용해야한다. => 그리고 만든 각각의 비트마스크에 대해서, 주어진 단어들과 비교해 읽을 수 있는 (단어 안에 쓰인 글자들이 모두 부분수열에 있는 문자들인 경우) 경우 cnt + 1 한다. => 궁금한 점 : alpha의 모든 부분집합을 다 테스트하는 것이 아니라, 7개만 뽑아서 테스트하는 것이다. 이를 예외처리할 수 있나?
alpha : antrcihelo a an
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
vector<string> words;
vector<char> alpha;
int findIndex(char c) {
for (int i = 0; i < (int)alpha.size(); i++) {
if (alpha[i] == c)
return i;
}
return -1;
}
int count() {
int m = alpha.size();
int ret = 0;
for (int i = 1; i < (1 << m); i++){ // alpha의 모든 집합을 검사
int cnt = 0; // 현재 글자 집합을 가르쳐 주었을 때 읽을 수 있는 단어 개수
for (string word : words){
bool flag = true; // 현재 단어를 읽을 수 있는지 저장
for (char c : word)
// 현재 집합에 현재 글자 c가 포함되어있지 않다면
if (!(i & (1 << findIndex(c)))) { // 요기 if문이 이상하다. !!!
flag = false;
break;
}
if (flag) cnt++; // 이 문자열은 읽을 수 있다.
}
if (ret < cnt) ret = cnt; // 읽을 수 있는 단어의 최대 개수를 저장한다.
}
return ret;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
string input; cin >> input;
words.push_back(input);
for (int k = 0; k < words[i].size(); k++)
// 처음 마주하는 글자라면
if (find(alpha.begin(), alpha.end(), words[i][k]) == alpha.end())
alpha.push_back(words[i][k]);
}
for (char a : alpha)
cout << a;
cout << endl;
cout << count() << endl;
return 0;
}
여기서 내가 놓친 것은, k를 7개 이하로 제한하지 않았다는 것이다. (사실 몰라서 못했는데 이게 틀린 원인이 될 줄 몰랐다 .. )
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
vector<string> words;
vector<char> alpha;
int findIndex(char c) {
for (int i = 0; i < (int)alpha.size(); i++) {
if (alpha[i] == c)
return i;
}
return -1;
}
// 현재 단어가 set 부분집합으로 모두 읽을 수 있는지 검사한다.
bool isSubset(string word, int set) {
for (char c : word) {
int index = findIndex(c);
if (index == -1 || !(set & (1 << index)))
return false;
}
return true;
}
int bitCount(int x) {
int ret = 0;
while (x) {
if (x & 1) ret++;
x >>= 1;
}
return ret;
}
int count() {
int m = alpha.size();
int ret = 0;
if (k < 5) return ret; // anta와 tica를 읽을 수 없음
if (k == 26) return n; // 모든 글자를 다 읽을 수 있는 경우, 모든 단어를 읽을 수 있다.
for (int i = 1; i < (1 << m); i++){ // alpha의 모든 집합을 검사
if (bitCount(i) != k) continue; // 집합에서 고른 글자의 개수가 k개가 아니면 연산하지 않는다.
int cnt = 0; // 현재 글자 집합을 가르쳐 주었을 때 읽을 수 있는 단어 개수
for (string word : words)
if (isSubset(word, i))
cnt++;
if (ret < cnt) ret = cnt; // 읽을 수 있는 단어의 최대 개수를 저장한다.
}
return ret;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
string input; cin >> input;
words.push_back(input);
for (int k = 0; k < words[i].size(); k++)
// 처음 마주하는 글자라면
if (find(alpha.begin(), alpha.end(), words[i][k]) == alpha.end())
alpha.push_back(words[i][k]);
}
cout << count() << endl;
return 0;
}