[백준] 19699: 소-난다! - JAVA

12 Jun 2023 in Algorithm on 수학

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

풀이

소 M마리의 합이 소수인지 판별하는 문제였다.

N마리의 소가 있다. N마리 중 M마리의 조합을 만들어 소수인지 판별해주었다.

소수는 에라토스테네스의 체를 구현하여 미리 배열에 정보를 담아놓았다.

오름차순으로 출력과 중복 제거를 위해 TreeSet을 이용했고, Set출력을 위해 Stream을 이용했다.

---

메모리: 14296KB

시간: 128ms

언어: Java 11

코드

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

public class Main {
    static int N, M;
    static int[] cow, group;
    static boolean[] prime;
    static TreeSet<Integer> ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cow = new int[N];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cow[i] = Integer.parseInt(st.nextToken());
            sum += cow[i];
        }

        prime = new boolean[sum + 1];
        prime[0] = prime[1] = true;
        for (int i = 2; i * i <= sum; i++) {
            if (!prime[i]) {
                for (int j = i * i; j <= sum; j += i) {
                    prime[j] = true;
                }
            }
        }

        ans = new TreeSet<>();
        group = new int[M];
        makeGroup(0, 0);

        if (ans.size() != 0) {
            ans.stream().forEach(num -> System.out.print(num + " "));
        } else {
            System.out.println(-1);
        }

    }

    private static void makeGroup(int cnt, int idx) {
        if (cnt == M) {
            int sum = 0;
            for (int i = 0; i < M; i++) {
                sum += group[i];
            }
            if (!prime[sum]) {
                ans.add(sum);
            }
            return;
        }

        for (int i = idx; i < N; i++) {
            group[cnt] = cow[i];
            makeGroup(cnt + 1, i + 1);
        }
    }

}