Cộng đồng Hỏi & Đáp của Inflearn

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

제출하니까 시간초과가 뜹니다. 어디가 잘 못 된건가요??

import java.io.*;
import java.util.*;

public class Main {
	public static int[] pow, st;
	public static int n,d,k,answer=Integer.MIN_VALUE;
	public static void main(String[] argvs) {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		d=sc.nextInt();
		k=sc.nextInt();
		pow = new int[d+1];
		st = new int[n+1];
		pow[1]=1;
		for(int i=2; i<=d; i++) pow[i] = pow[i-1]*2;
		
		for(int i=1; i<=n; i++) {
			int num, m;
			m=sc.nextInt();
			for(int j=0; j<m; j++) {
				num=sc.nextInt();
				st[i] += pow[num];
			}
		}
		dfs(0,0,0);
		System.out.print(answer);
	}
	public static void dfs(int L, int s, int bit) {
		if(L==k) {
			int cnt=0;
			for(int i=1; i<=n; i++) 
				if((bit&st[i])==st[i])cnt++; //st[i]가 bit의 부분집합이라면 cnt증가
			answer = Math.max(answer, cnt); //최대값 갱신
		}
		else {
			for(int i=s; i<d; i++) { //조합으로 탐색
				dfs(L+1, i+1, bit+pow[i]);
			}
		}
	}
}