[백준BOJ] 15649번 N과 M(1).java

 

백준 저지에서 N과 M(1)을 자바를 통해 풀어 보았다. 

 

15649번 N과 M(1).java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

15649번 N과 M(1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

설명

예전에 파이썬으로도 한 번 풀어봤던 문제인데 다시 한 번 또 풀어보았다.

 

순열문제이면 백트래킹을 통해 순열을 구현하여 완전 탐색하면 된다.

코드

//15649번 N과 M(1).java
package week5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N과_M1_15649 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static int N;
    static int M;
    static boolean[] isSelected;
    static int[] select;
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		isSelected = new boolean[N];
		select = new int[M];
		P(0);
		System.out.println(sb.toString());
	}
    
    public static void P(int count) {
    	if(count==M) {
    		for(int i=0;i<M;i++) {
    			sb.append(select[i]+" ");
    		}sb.append("\n");
    		return ;
    	}
    	for(int i=0;i<N;i++) {
    		if(!isSelected[i]) {
    			isSelected[i]=true;
    			select[count] = i+1;
    			P(count+1);
    			isSelected[i]=false;
    		}
    	}
    }
}