백준 15649, N과 M (1)

문제

문제요약

1. 1~N까지의 자연수 중에서 M개를 고른 수열을 출력하십시오.

 

문제풀이

순열을 출력하기 위해서 아래 가지치기와 같은 과정을 수행합니다.

위의 그림과 같이 순열을 생성하는 과정은 재귀적으로 수행되어야 합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;


public class Main {
	static int N, M;
	static List<Integer> permutation = new ArrayList<Integer>();
	static boolean[] chosen;
	
	public static void search()
	{
		if(permutation.size()==M)
		{
			permutation.stream().forEach(item -> System.out.print(item + " "));
			System.out.println();
		}else {
			for(int i=1;i<=N; i++)
			{
				if(chosen[i])
				{
					continue;
				}
				chosen[i] = true;
				permutation.add(i);
 				
				search();
				
				chosen[i] = false;
				permutation.remove(permutation.size()-1);
			}
		}
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		chosen = new boolean[N+1];
		
		search();
	}
}

References

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드