글 읽기 - 1062번 뭐가 틀렸는지 잘 모르겠습니다.

amjong 5년 전 0

a, c, i, n, t 5개를 제외하고

21개 중 K-5개를 뽑는 모든 경우의 수에 대해서

읽을 수 있는 단어의 수를 세서 그 중 최댓값을 취하는 방식으로 구현했는데요

21개 중 K-5개를 뽑는 모든 경우의 수는

단순하게 재귀호출로 구현했고

함수 호출 과정 도중에 현재 뽑은 알파벳의 정보는

매개변수인 int check에 비트마스킹 형식으로 담았습니다.

(abc 배열에 제외할 알파벳들 제외한

21개의 알파벳들을 넣어놓고(인덱스 0~20)

해당 인덱스로 알파벳을 뽑았는지 안뽑았는지를 판별)

ex) check & (1 << 3) != 0 이면, abc[3]인 'f'를 뽑은 상태.

코드가 좀 난잡하긴 한데(ㅠㅠ) 도와주시면 감사하겠습니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int n, k;
string str;
vector<string> s;
char abc[] = { 'b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 'q', 'r', 's', 'u', 'v', 'w', 'x', 'y', 'z' }; 
// (a, c, i, n , t)를 제외한 알파벳들
int abc_idx[] = { -1, 0, -1, 1, 2, 3, 4, 5, -1, 6, 7, 8, 9, -1, 10, 11, 12, 13, 14, -1, 15, 16, 17, 18, 19, 20 };
// 각각의 알파벳이 abc배열의 어느 인덱스에 있는지 정보를 담고 있는 배열 ex) 'b' => abc_idx['b' - 'a'] = 0, 0번 인덱스에 존재
int ans = -1;
void dfs(int check, int idx, int cnt);
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;	
	getchar();
	for (int i = 0; i < n; i++) {
		getline(cin, str);
		s.push_back(str);
	}
	if (k < 5) { // k가 5보다 작으면 모든 단어를 배울 수 없음.
		cout << 0;
		return 0;
	} 
	dfs(0, -1, 0);
	cout << ans;
}
void dfs(int check, int idx, int cnt) { // check : abc배열의 0~20 인덱스(총 21개) 중 현재 선택한 인덱스는 1, 아닌 인덱스는 0(비트마스킹)
										// idx : 0~20 인덱스 중 dfs탐색을 시작할 인덱스
										// cnt : 여태까지 뽑은 갯수
	if ((21 - idx) < ((k - 5) - cnt)) return;
	if (cnt == k - 5) { // k - 5개를 다 뽑았으면
		int ret = 0;
		for (int i = 0; i < n; i++) { // n개의 모든 단어들에 대해서 읽을 수 있는 단어의 갯수를 구함.
			string temp = s[i];
			bool result = true;
			int temp_size = temp.size();
			for (int j = 4; j < temp_size - 4; j++) { // 처음 +4 ~ 마지막 - 4 (anta와 tica 사이 단어에 대해 체크)
				char now = temp.at(j);
				if (abc_idx[now - 'a'] == -1) continue; // (a,c,i,n,t)인 경우
				else {
					if ((check & (1 << abc_idx[now - 'a'])) == 0) { // 이번 알파벳이 뽑히지 않은 알파벳일 경우 
						result = false; // 배울 수 없는 단어이므로 false처리.
						break;
					}
				}				
			}
			if (result) ret++; // 이 단어의 모든 알파벳이 K-5개 중 뽑힌 알파벳일 경우 배울 수 있는 단어이므로 갯수 + 1
		}
		if (ans < ret) ans = ret; // n개의 단어에 대해 보고, 배울 수 있는 단어의 갯수에 대해 최댓값 갱신
		return;
	}
	else {
		for (int i = idx + 1; i < 21; i++) {
			dfs(check | (1 << i), i, cnt + 1); // dfs 순차 탐색		
		}
	}
}

amjong 5년 전 0

처음에 단어들 n개 입력받을 때

getline(cin, str);

로 받았었는데

cin >> str;

로 변경하니까 바로 해결됐습니다

(...)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1062번 뭐가 틀렸는지 잘 모르겠습니다.

amjong 5년 전 0

amjong 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말