[문제 풀이] 백준 15654번 N과M(5) JAVA

문제

  문제접근 방법   

해당 문제는 N과 M이 각각 주어진다고 했을 때, N개의 자연수 중에서 M개를 고른 수열을 구하는 프로그램을 작성하는 문제로

N개의 자연수는 입력받는다.

앞서 풀었던 N과 M 문제들과 유사하지만 조금 다르다. 먼저 배열 arr를 선언하고 N개의 자연수를 입력받는다. 이후 사전 순으로 증사하는 순서라는 조건을 충족하기 위해서 배열 arr를 정렬해준다. 그리고 예제 출력에서도 확인해볼수 있듯이 하나의 수열에는 같은 숫자가 들어갈수 없다. 그래서 어떤 숫자를 사용했는지 확인하기 위해 백트래킹을 활용해 접근하였다 코드는 아래와 같다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static int num[];
    public static void main(String arg[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        int arr[]=new int[n+1];
        visited=new boolean[n+1];
        num=new int[m];
        for(int i=1;i<=n;i++){
            arr[i]=s.nextInt();
        }
        Arrays.sort(arr);
        dfs(0,n,m,arr);
    }
    public static void dfs(int depth,int n,int m,int arr[]){
        if(depth==m){
            for(int i=0;i<m;i++){
                System.out.print(num[i]+" ");
            }System.out.println();
            return;
        }
        
        for(int i=1;i<=n;i++){
            if(!visited[i]){
                visited[i]=true;
                num[depth]=arr[i];
                dfs(depth+1,n,m,arr);    
                visited[i]=false;
            }
        }
        

    }
}

위에서 설명하였듯이 arr에 N개의 숫자를 입력받고 Arrays.sort를 통해서 오름차순으로 정렬한후 탐색하는 방식으로 코드를 작성하였다.

  N과 M시리즈   

https://hmkang32180116.tistory.com/127

[문제 풀이] 백준 15649번 N과 M(1) JAVA _다시풀이

 

https://hmkang32180116.tistory.com/132

[문제 풀이] 백준 15650번 N과 M(2) JAVA

 

https://hmkang32180116.tistory.com/178

[문제 풀이] 백준 15651번 N과 M(3) JAVA

 

https://hmkang32180116.tistory.com/179

[문제 풀이] 백준 15652번 N과 M (4) JAVA