[백준] 15649번 N과 M - 1 (C++, JAVA)

15649번: N과 M (1)

N개 중에 중복 미 포함, 순서를 고려하여 M개를 뽑는 순열 문제이다.

바로바로 출력을 할 수 없기 때문에 벡터를 만들어 값을 저장하고 빼주면서 출력해준다.

 

대충 이런 식으로 돌아가는 구성이다.

 

< C++ 코드 >

#include <iostream>
#include <vector>
using namespace std;
vector <int> v;
int check[10] = { 0 };

int cnt = 0;
void permutation(int N, int M) {
	if (cnt == M) {
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	}
	else {
		for (int i = 0; i < N; i++) {
			if (check[i] == 0) {
				check[i] = 1;
				v.push_back(i + 1);
				cnt++;
				permutation(N, M);
				v.pop_back();
				cnt--;
				check[i] = 0;
			}
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
    
	permutation(N, M);

	return 0;
}

 

< JAVA 코드 >

public class BOJ_15649_N과M_1{

	public static int N, M;
	public static int arr[];
	public static boolean chk[];
	
	public static void permutation(int cnt) {
		if(cnt == M) {
			for(int val : arr) System.out.print(val + " ");
			System.out.println();
			return;
		}
		for(int i = 0; i < N; i++) {
			if(chk[i]) continue;
			chk[i] = true; arr[cnt] = i + 1;
			permutation(cnt + 1);
			chk[i] = false; 
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();M = sc.nextInt();
		chk = new boolean[N];arr = new int[M];
		permutation(0);
	}
    
}