재귀로 탐색 시 종료조건에 대한 문의입니다.

작성한 질문수 3

0

안녕하세요 98님 ㅎㅎ

잘 짜셨고 26으로 해도 맞게 나올 수 있습니다. 다만 우선순위 문제인 거 같아요.

이걸 잠깐 볼까요?

		if (!(mask & (1<<v))) {
			mask |= (1<<v);
			dfs(v+1, on+1);

자 지금 보면 해당 v번째를 추가하고 ~~ dfs v + 1을 통해서 v + 1에서 종료를 시키고 있죠?

0부터 시작해볼께요.

0, 0

>>

1, 1을 하면서 0을 집어넣었다. 라는 뜻으로 되는 거구요.

쭉 이렇게 가다보면

25, 5 가 되고 이는 24를 집어넣었다. 가 되고

그 다음.

26, 6 이는 25를 집어넣었다. 가 됩니다.

근데 여기서 26일 때 종료를 시키면

해당 26을 집어넣었을 때의 이로직보다.

if (on==k) {
		int cnt = 0;
		for (int i=0; i<n; i++) {
			int word = words[i];
			if ((word&mask) == word) cnt++;
		}
		ret = max(ret, cnt);
		return;
	}

다음 로직이 먼저 실행이 되겠죠?

	if (v==26) return;

그러면 26을 집어넣었을 때의 해당 카운팅 로직이 실행될까요?

안되겠죠?

그럼 어떻게 코드를 수정해야할까요?

다음과 같이 우선순위를 고치시면 됩니다.

#include<bits/stdc++.h>
using namespace std;

int n,k,words[51], mask, ret;
string s, need = "acint";

void dfs(int v, int on) {  
    if (on==k) {
		int cnt = 0;
		for (int i=0; i<n; i++) {
			int word = words[i];
			if ((word&mask) == word) cnt++;
		}
		ret = max(ret, cnt);
		return;
	} 
	if (v==26) return; 
    if (!(mask & (1<<v))) {
        mask |= (1<<v);
        dfs(v+1, on+1);
        mask &= (~(1<<v));
    }
    dfs(v+1, on); 
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> k;
	for (int i=0; i<n; i++) {
		cin >> s;
		s= s.substr(4, s.size()-8);
		for (char c : s) {
			words[i] |= (1 << (c-'a'));
		}
	}
	if (k < 5) {
		cout << "0" << '\n';
		return 0;
	}
	for (char c : need) {
		mask |= (1 << (c-'a'));
	}
	k -=5;
	dfs(0,0);
	cout << ret << '\n';
}

감사합니다.