[알고리즘] 백준 15665 N과 M(11) -백트래킹- 자바

 

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

15665번: N과 M (11)

 

백준 백트래킹 문제 시리즈로 유명한 N과 M 시리즈의 11번째 문제를 풀어봤습니다.

같은 수를 여러번 고를 수 있는 순열조합이므로 중복 선택을 체크할 boolean[] isVisited 는 사용하지않았습니다.

 

 

풀이는 다음과 같습니다. 

 

[Java]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N;
    private static int M;
    private static int[] nums;
    private static StringBuilder sb = new StringBuilder(); //사용안하면 시간초과남

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        //수열은 사전 증가하는 순서대로 출력해야함
        Arrays.sort(nums);
        dfs(0,new int[M]);
        System.out.println(sb.toString());
    }

    private static void dfs(int depth, int[] arr) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prev = -1;
        for (int i = 0; i < N; i++) {
            if (prev != nums[i]) { // 중복되는 수열 여러번 출력되는거 방지
                prev = nums[i];
                arr[depth] = prev;
                dfs(depth + 1, arr);
            }
        }
    }
}

https://github.com/mtjin/algorithm_practice/commit/c0c5932472d72cd0989c99b7f1fb4bb13033f308

백준 15665 풀이 · mtjin/algorithm_practice@c0c5932

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!