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

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

19699번: 소-난다!

 

문제

 

입력

 

출력

 

---

소스코드

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

public class Main {
    static int n, m;
    static int arr[];
    static ArrayList<Integer> al = new ArrayList();

    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());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        backtrack(0, 0, 0);

        Collections.sort(al);
        for (int i : al) {
            System.out.print(i + " ");
        }

        if (al.size() == 0) System.out.print(-1);
    }

    static void backtrack(int x, int sum, int cnt) {
        if (cnt == m) {
            //소수 판별
            for (int i = 2; i <= sum / 2; i++) {
                if (sum % i == 0) return;
            }
            if (!(al.contains(sum))) al.add(sum);
        }

        for (int i = x; i < n; i++) {
            backtrack(i + 1, sum + arr[i], cnt + 1);
        }
    }
}

 

해결 방법

1. M마리 소들의 몸무게 합으로 만들 수 있는 모든 소수를 구하려면 완전 탐색을 진행해야하고 이때 백트래킹을 사용하였다.
2. 백트래킹을 할 때 주의점으로 몸무게 합이 소수인 M마리 소들을 택했을 때, 해당 몸무게 합이 이미 리스트에 있다면 저장하지 않아야 한다. 그래야 중복된 값을 출력하지 않는다.