Submission #54608270

---

Source Code Expand

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 売り場の数
        int M = sc.nextInt(); // 味の種類の数
        sc.nextLine(); // 改行を消費

        List<Set<Integer>> popcornInfo = new ArrayList<>();

        // 各売り場の情報を読み取る
        for (int i = 0; i < N; i++) {
            String s = sc.nextLine();
            Set<Integer> tastes = new HashSet<>();
            for (int j = 0; j < M; j++) {
                if (s.charAt(j) == 'o') {
                    tastes.add(j);
                }
            }
            popcornInfo.add(tastes);
        }

        int minCount = N; // 最大N個の売り場を訪れる可能性があるので、初期値をNに設定

        // 2^N通りの組み合わせを試行
        for (int i = 0; i < (1 << N); i++) {
            Set<Integer> allTastes = new HashSet<>();
            int count = 0;
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) != 0) {
                    allTastes.addAll(popcornInfo.get(j));
                    count++;
                }
            }
            // すべての味をカバーしているか確認
            if (allTastes.size() == M) {
                minCount = Math.min(minCount, count);
            }
        }

        // 結果を出力
        System.out.println(minCount);
    }
}

Submission Info

Judge Result