[JAVA] 백준 15650

 

 

15650번: N과 M (2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

풀이

이전 문제인 15649(https://g-db.tistory.com/entry/JAVA-백준-15649)와 비슷한 문제지만 다른 점은 수열의 수를 선택한 적이 있는 경우 사용할 수 없다는 점이다.

📌 백트래킹 탐색

    static void DFS(int depth, String value, int now){
        if(depth == M){
            sb.append(value.substring(1)).append("\n");
            return;
        }

        for(int i=now; i<N; i++){
            if(!V[i]){
                V[i] = true;
                DFS(depth+1, value + " " + i, i);
                V[i] = false;
            }
        }

    }

이 수열의 특징은 현재 자신의 값 보다 작은 값들은 이미 앞에서 수열로 출력되기 때문에 반복의 시작이 현재 자신의 값부터 시작하면 된다.

📌 전체 코드

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

class Main {

    static boolean[] V;
    static int M;
    static int N;
    static StringBuilder sb = new StringBuilder();
    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())+1;
        M = Integer.parseInt(st.nextToken());

        V = new boolean[N];

        DFS(0, "", 1);
        System.out.println(sb);

    }

    static void DFS(int depth, String value, int now){
        if(depth == M){
            sb.append(value.substring(1)).append("\n");
            return;
        }

        for(int i=now; i<N; i++){
            if(!V[i]){
                V[i] = true;
                DFS(depth+1, value + " " + i, i);
                V[i] = false;
            }
        }

    }

}

결과