코딍코딍
코딩기록
코딍코딍
전체 방문자
오늘
어제
  • 분류 전체보기 (271)
    • 개발 (2)
    • Java (1)
    • 스프링 (28)
    • JPA (11)
    • Git (3)
    • 알고리즘 (160)
      • 백준 (132)
      • 프로그래머스 (8)
      • SWEA (20)
    • 토이 프로젝트 (14)
      • 간단한 Springboot CRUD (1)
      • 게시판 프로젝트 (13)
    • 알고리즘 개념정리 (8)
    • 오류 해결 (13)
    • 보류 (0)
    • AWS (5)
    • 트러블 슈팅 (0)
    • 회고 (3)
    • CS (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

최근 글

티스토리

hELLO · Designed By 정상우.
코딍코딍

코딩기록

알고리즘/백준

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

2024. 1. 29. 21:10

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

 

해결 방법

  1. M마리 소들의 몸무게 합으로 만들 수 있는 모든 소수를 구하려면 완전 탐색을 진행해야하고 이때 백트래킹을 사용하였다.
  2. 백트래킹을 할 때 주의점으로 몸무게 합이 소수인 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
    '알고리즘/백준' 카테고리의 다른 글
    • [백준] 1326번 : 폴짝폴짝
    • [백준] 21608번 : 상어 초등학교
    • [백준] 13549번 : 숨바꼭질 3
    • [백준] 2468번 : 안전 영역
    코딍코딍
    코딍코딍
    ㅎ2

    티스토리툴바