https://www.acmicpc.net/problem/19699
19699번: 소-난다!
지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐
www.acmicpc.net
문제
입력
출력
소스코드
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);
}
}
}
해결 방법
- M마리 소들의 몸무게 합으로 만들 수 있는 모든 소수를 구하려면 완전 탐색을 진행해야하고 이때 백트래킹을 사용하였다.
- 백트래킹을 할 때 주의점으로 몸무게 합이 소수인 M마리 소들을 택했을 때, 해당 몸무게 합이 이미 리스트에 있다면 저장하지 않아야 한다. 그래야 중복된 값을 출력하지 않는다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1326번 : 폴짝폴짝 (2) | 2024.02.04 |
---|---|
[백준] 21608번 : 상어 초등학교 (0) | 2024.01.28 |
[백준] 13549번 : 숨바꼭질 3 (0) | 2024.01.23 |
[백준] 2468번 : 안전 영역 (0) | 2024.01.22 |
[백준] 11660번 : 구간 합 구하기 5 (0) | 2024.01.22 |