백준 16457 JAVA : 단풍잎 이야기

문제

https://www.acmicpc.net/problem/16457

16457번: 단풍잎 이야기

 

풀이 예상

완전탐색 => 모든 숫자들의 조합을 만들어서 퀘스트를 몇 번 할 수 있는지 세 본다.

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(2^n)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_16457 {
    static  int n, m, k, answer;
    static List<Integer>[] list;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        list = new ArrayList[m];
        for (int i = 0; i < m; i++) {
            list[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < k; j++) {
                list[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        visited = new boolean[2*n+1];
        answer = 0;
        
        combi(0,1);

        System.out.println(answer);

    }
    static void combi(int depth, int start) {
        if(depth == n) {

            int result = 0;
            for (int i = 0; i < m; i++) {
                int count = 0;
                for (int j = 0; j < k; j++) {
                    if(visited[list[i].get(j)]) count++;
                }
                if(count == k) result++;
            }

            answer = Math.max(answer, result);

            return;
        }
        for (int i = start; i <= 2*n; i++) {
            visited[i] = true;
            combi(depth+1, i+1);
            visited[i] = false;
        }

    }
}

 

결과