백준 JAVA11 18429번 : 근손실

BackTracking, DFS

문제 상세보기

Flow.

• 모든 경우의 수를 검사해서 조건에 맞는 경우를 카운트해서 출력해주는 알고리즘입니다.
• 리스트 & 정렬 사용
  • 정렬을 사용함으로써 운동키트 효과가 작은 순서대로 정렬시킬수 있습니다.
  • 작은 순서대로 정렬한다면 감소량 K보다 작은 경우의 수들이 빠르게 걸러지고 탐색을 하지 않음으로 백트래킹이 가능합니다.
• backTracking(int sum, int depth)
  • depth == n - 1 에 도달하면 하나의 경우의 수는 모두 탐색했음으로 카운트++ & 탈출조건을 만들어줍니다.
  • 반복문에서 recursion을 통해 방문하지 않았고, 합계(500) + 운동키트 효과 - 감소량이 500 이상인 경우만 탐색합니다.
  • 방문한 운동키트는 true로 바꾸어 줍니다.
• visited[i] = false;
  • 해당 (arr.get(i)) 운동키트를 선택한 모든 경우의 수를 탐색했기 때문에 첫번째 운동키트 사용 여부를 다시 원상복귀 해주어야 합니다.

Code.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    static int n;
    static int k;
    static int count;
    static List<Integer> arr;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); //운동키트 갯수 & n 일
        k = scanner.nextInt(); //감소량

        arr = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> arr.add(scanner.nextInt()));
        arr.sort(Comparator.naturalOrder());

        visited = new boolean[n];
        count = 0;
        backTracking(500, 0);
        System.out.println(count);
    }

    private static void backTracking(int sum, int depth) {
        if (depth == n - 1) {
            count++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i] && sum + arr.get(i) - k >= 500) {
                visited[i] = true;
                backTracking(sum + arr.get(i) - k, depth + 1);
                visited[i] = false;
            }
        }
    }
}