글 읽기 - 시간초과 질문입니다!

skyinyour 4년 전 0

비트 마스크로 모든 조합을 고려하여서 단어들의 부분집합이 이루는 문장이 26개의 알파벳을 모두 가지고 있는지 확인해보려 하였습니다.

dfs 보다 빠를 것이라 생각했는데 시간 초과인데 아래 코드에서 어느 부분이 문제인지 알 수 있을까요?

#include <iostream>
#include <string.h>

using namespace std;

int N;
char str[27][101];

// a: 97  z : 122
int check[123];


int main() {

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> str[i];
	}
	int ans = 0;
	int flg = 0;
	int pow = 1 << N;

	for (int i = 1; i < pow; i++) {
		
		int cmp = (1 << 26) - 1;
		int cmp2 = 0;
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) {

				for (int k = 0; str[j][k] != '\0'; k++) {
					//check[str[j][k] - '\0'] = 1;
					int p = str[j][k] - '\0' - 97;
					cmp2 |= (1 << p);
				}

			}
		}
		if (cmp2 == cmp) {
			ans++;
		}

	}
	cout << ans;
	return 0;
}

kcm1700 4년 전 0

단순 연산 회수만 따져도 2^25*25/2*100=41943040000 > 4백억 너무 큰데요

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

문제

문제

출처

ICPC

시간초과 질문입니다!

skyinyour 4년 전 0

kcm1700 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말