| 1 초 | 128 MB |
문제
남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.
남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.
출력
첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.
1. 문제 해석.
김지민 선생이 K개의 글자를 가르킬 때 주어진 단어들을 사전이라고 보고,
그 사전에서 몇개의 단어를 읽을 수 있는지 세는 문제이다.
1) 문제 접근은 처음에 사전에서 받은 단어를 바탕으로,
단어 내의 글자 중 'anta' 와 'tica' 사이에 있는 문자를 하나씩 K-5개로 조합하여 배웠다고 치고
읽을 수 있는 단어를 세려고 했다.
이때 K-5개인 이유는 이미 anta, tica 에 속한 a,n,t,c,i 5글자는 무조건 배워야 하기 때문이다.
그러나 이 방법으로 하니 시간초과가 떴다.
힌트를 보니 비트 마스크를 써서 효율성있게 짜야하는 문제였다.
1-1. 비트 마스크
비트 연산 : 이진수의 의미를 활용하여, 비트 연산에 의미를 부여하여 문제를 풀 수 있다.
여기에서는 알파벳이 26자로 정해져있다는 것이 힌트이다.
이진수의 각 26자리의 1, 0 여부가 배웠는지 안 배웠는 지 여부 , 또는 단어를 이루는 글자요소를 나타내는 의미를 나타낼 수 있다는 것이다.
그렇다면 26자리 비트를 표현할 방법은?
int형이 8byte로 32bit이기 때문에, Int형만 사용해도 쉽게 표현할 수 있다.
(말은 쉽게라고 하지만 사실 10진수로 검색한 다음에 에 안되겠네.. 하고 26자를 13자로 반으로 쪼개서 어렵게 비트를 구현했던 과거의 나였다ㅏㅏㅏ)
그래서 그 다음으로 비트 연산을 알아보자.
일전에 https://ebang.tistory.com/8 이곳에서 쉬프트 연산 등 개념을 정리했었는데
막상 문제에 적용하려니 좀 어려웠다.
우선 + 가 아니라 | 연산으로 비트를 더해야 했는데 그것도 틀렸었고,
이미 원하는 자리에 0이 있는지 확인하고 싶을 때 (해당 위치에 1이 있는 수와&연산) 을 통해 0이라면 사실이라고 판별할 수 있는 사항에 대해 사실XOR을 써버려서, 그 위치를 제외하고는 다 1111011111이런 수인지 확인하는 이상한 논리로 짠 경우도 있었다.
그래서 일단 정리하자면
- 비트 더하기 |
- 비트 AND 연산하기 &
- 비트 XOR 연산 하기 ^
- 어떤 이진수의 5번째 자리에 숫자가 0인지 확인하기: 00001 0000(다른 자리는 다 0이어야 한다.)와 &연산을 수행해서 0인지 확인
[어떤 이진수] [AND 연산할 수]
-> 11001 0000 & 00001 0000 = 00000 0000
-> 11001 0000 & 10111 0000 = 10001 0000 -> 다섯번째가 1이고 나머지는 모두 1인 이진수와 & 연산해야 한다.
- 어떤 두 이진 수가 서로 포함관계에 있는지 확인하기
ex) A = 0100, B = 0101. -> A가 B에 속해있다면, A와 B를 연산해도 그대로 A일 것이다. (1로 겹치는 부분은 1로, 나머지는 0이 될 것이므로 나머지라는 것은 A가 B와 달리 0인 위치.)
1-2) 백트레킹
조합을 만들 수 있는 가장 좋은 (사실 내가 알고 있는 유일한 빠른) 방법이다.
기본적으로 어떤 n개의 숫자 중에서 k를 선택하려고 할 때,
n개 중 k를 뽑고 나면 그 순서는 상관이 없다. (1,2,3 을 뽑든 2,1,3을 뽑든. )
하지만 그 순서를 오름차순으로 정렬해두면 경우의 수는 오직 한가지이다.
무슨 말이냐 하면, 순서대로 k개를 뽑는다면 그게 곧 k개로 만들 수 있는 여러 조합 중 유일한 방법이 될 것이라는 소리다.
(1,2,3 , 2,1,3, 3,2,1 , 1,3,2 같은 모든 경우의 수를 1,2,3으로 보자는 이야기이다.)
직관적으로도 이해가 된다.
1~5의 수를 3개 뽑는 경우의 수를 생각해보려고 한다면,
직관적으로 (123) (124) (125) (134) (135) (145) 이렇게 큰 순으로 일련의 규칙아래 세기 때문이다.
이 직관을 그대로 적용한게 백트레킹이다.
내가 뽑으려는 집합에서 가장 작은 시작점을 index, 뽑으려는 개수를 count라고 설정하면
void Combination(int index, int cnt)
{
//base case
if(cnt == target)
{
//do something
return;
}
for(int i=index;i<N;i++)
{
select.push(i);
Combination(i + 1, cnt + 1);
select.pop();
}
}이런식으로 조합을 만들 수 있는데,
Combination(1, 0)으로 시작하면
N(예시에서처럼 5)에 도달하기 전까지
Combination(2,1)
Combination(3,2)
Combination(4,3)이 순서대로 스택에 쌓일 것이고, cnt == target인 3과 같아지면 원하는 수행을 한뒤
(보통 select에 저장해둔 인덱스로 조합을 선택해서 표시해주고 진행)
return 되면, 직전의 위치였던 Combination(3,2)로 돌아가서 for문이 진행된다. 즉
select.pop() 이 되어 (3)이 빠져나오고 i=4일 때 push 후에 Combination(5,3)이 수행된다.
이 과정을 쭉 하다보면 (1,2,3) , (1,2,4) ... (3,4,5)까지 만들어지면서 base case에서 조합이 만들어 진뒤 무언가를 할 수 있는 것이다.
이때 주의할 사항은 i를 넣어서 원하는 값을 넣어야 한다는 거다.
보통 재귀함수 쓸 때 처럼 index를 활용해서 combination(index + 1)같은 실수를 하지 말도록 하자.
2. 구현
그래서 내가 짠 코드는 다음과 같다.
#include <iostream>
#include <queue>
#include <vector>
#include <queue>
#define MAX 51
using namespace std;
int N, K;
string s[MAX];
int word[MAX];
int learned;
vector <char> selected;
int answer = 0;
void input()
{
string str;
for(int i=0;i<N;i++)
{
cin >> str;
for(int j=0;j<str.size();j++)
{
if((word[i] & ( 1 << str[j] - 'a')) == 0) {
word[i] |= (1 << str[j] - 'a');
}
}
}
}
void find_learned()
{
//1.배운 단어들을 배웠다고 표시
//2.읽을 수 있는 단어들 세기
//-> 더 나은 시간 복잡도를 위해서 비트 연산으로 풀어보자.
//비트 연산: 합도 |= 로 더해야 한다.
//string [i] = a의 경우 value |= (1 << string[i] -'a') 를 하면 0000 0000 0000 0000 0001 처럼 설정된다.
//총 26개의 비트가 필요한데 int형은 32bit로, 표현이 가능하다. (십진수로 몇자리수인가와는 상관이 없다)
//3.최댓값 갱신
//4.그다음 풀이를 위해 다시 선택된 단어 되돌리기.
// cout << "start " <<"\n";
for(int i=0;i<selected.size();i++)
{
//cout << "selected : " << selected[i] << " ";
if((learned & (1 << (selected[i] - 'a'))) == 0)
learned |= (1 << (selected[i] - 'a'));
}
// cout << "\n";
int cnt = 0;
for(int i=0;i<N;i++)
{
if((word[i] & learned) == word[i]) {
//cout << i << "\n";
cnt++;
}
}
if(cnt > answer)
answer = cnt;
// 4. 그다음 풀이를 위해 다시 선택된 단어 되돌리기.
for(int i=0;i<selected.size();i++)
{
// cout << "selected : " << selected[i] << " ";
learned &= ~(1<< (selected[i] - 'a'));
}
}
void comb(int index, int cnt, int v)
{
//기저조건
if(cnt == v)
{
//단어 세기
find_learned();
return;
}
for(int i = index; i < 26;i++)
{
if((learned & (1 << i)) == 0)
{
// cout << "index : " << i << "\n";
selected.push_back(i + 'a');
comb(i + 1, cnt +1 , v);
selected.pop_back();
}
}
}
int solve()
{
if(K < 5)
return 0;
//문자를 조합해서 각 조합별로 단어들을 순회하면서 읽을 수 있는 단어를 센다.
//조합: 백트레킹
learned |= (1 << ('a' - 'a'));
learned |= (1 << ('n' - 'a'));
learned |= (1 << ('t' - 'a'));
learned |= (1 << ('i' - 'a'));
learned |= (1 << ('c' - 'a'));
comb(0,0,K-5);
return answer;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
input();
cout << solve();
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
| 백준 1039 - 교환 (안보이는 DFS, BFS) (0) | 2023.02.07 |
|---|---|
| 백준 5719 - 거의 최단경로 (0) | 2023.01.26 |
| 백준 11724 - 연결요소의 개수 - 그래프 탐색 및 순회 (0) | 2023.01.20 |
| 백준 7453 네 수의 합 - 투 포인터 알고리즘 (0) | 2023.01.19 |
| 백준 10250번 - ACM 호텔 (0) | 2023.01.17 |