백준 1062번 가르침

< 백준 1062번 가르침 - 마포 코딩박 >

사용한 알고리즘: 완전탐색, DFS


 N개의 단어들과, 선택 가능한 글자수 K가 주어집니다. a~z 중 K개를 선택해 주어진 N개의 단어들 중 최대 몇개의 단어를 읽을 수 있는지 확인하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) a = 0, b = 1, ... z = 25 로 생각했습니다.

(2) (코드: 41~45)
모든 단어는 "anta" 로 시작, "tica" 로 끝나므로, 기본적으로 a,n,t,i,c는 필요합니다.

(3) (코드: 13~37)
K-5 개의 글자를 추가로 뽑을 수 있습니다. (K<5 이면 단어를 하나도 읽을 수 없습니다.)
기본 5글자를 제외한 모든 글자를 추가로 뽑아보면서, 만약 K-5개를 뽑았을 경우 몇개의 단어를 읽을 수 있는지 확인해줍니다.
이를 DFS 로 돌렸습니다.

풀어보니 불필요한 부분이 많이 보이는.... 부끄러운 코드가 완성됐습니다...
깔끔하지 못한 코드 죄송합니다.

	#include <bits/stdc++.h>
	using namespace std;
	// a, b, c, ... z 를 0, 1, 2, ... 25 으로 저장
	int N, K, ans, CNT;
	// 각 단어들이 기본 5글자 이외에 필요한 글자 수
	int num[50];
	set<int> base;
	// arr[i][j]=true : i번째 단어는 j 글자가 필요함
	// 예를들어 j=3인 경우 c필요, j=4인 경우 d 필요
	bool arr[50][26];
	bool choice[26];
	// a~z (0~25) 다 넣어봄
	void DFS(int idx, int number){
	// K-5개의 추가 글자를 뽑은경우
	if(number==CNT){
	int Can=0;
	// N개 단어중 몇개 읽을 수 있는지
	for (int i = 0; i < N; ++i){
	int tt = 0;
	for(int j = 0; j<26; ++j)
	if(choice[j] && arr[i][j]) tt++;
	if(tt>=num[i]) Can++;
	}
	ans = max(Can,ans);
	return;
	}
	if(idx>=26) return;
	// 일단 해당 idx 안넣고 다음
	DFS(idx+1,number);
	// 해당 idx 가 기본 5글자중 하나면 pass
	if(base.count(idx)) return;
	// idx 글자 뽑았다 생각
	choice[idx]=true;
	// number: 뽑은 숫자 ++
	DFS(idx+1,number+1);
	// DFS 나오면 다시 뽑았던거 초기화
	choice[idx]=false;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> K;
	// 무조건 필요한 글자 5가지
	base.insert('a'-'a');
	base.insert('n'-'a');
	base.insert('t'-'a');
	base.insert('i'-'a');
	base.insert('c'-'a');
	for (int i = 0; i < N; ++i){
	string A;
	cin >> A;
	for(auto curr: A)
	// 기본 5글자가 아닌 경우 추가로 필요함
	if(!base.count(curr-'a'))
	arr[i][curr-'a'] = true;
	}
	for (int i = 0; i < N; ++i){
	int ccc = 0;
	for (int j = 0; j < 26; ++j)
	if(arr[i][j]) ccc++;
	// 각 단어들이 기본 5글자 이외에 필요한 글자들 수 저장
	num[i] = ccc;
	}
	// 기본 5글자는 무조건 필요함
	CNT = K-5;
	// 기본 5글자도 못선택하면 한단어도 읽을 수 없음
	if(CNT<0) cout << 0 << '\n';
	// DFS 탐색
	else{
	DFS(0,0);
	cout << ans << '\n';
	}
	return 0;
	}

view raw BOJ 1062.cpp hosted with ❤ by GitHub