{% embed url=“https://www.acmicpc.net/problem/15649” %}
Solution 1. 재귀함수,visited
•
79996 kb / 2980 ms
•
1부터 N까지의 자연수 중에서 M개를 중복없이 뽑는 경우의 수를 구하는 문제이므로 순열 알고리즘을 사용했다.
◦
visited 를 이용하여 dept 가 깊어질수록 하나씩 고정되어 트리의 앞쪽부터 순서대로 찾아 depth와 일치되는 즉시 출력하도록 하였다.
package practice.algorithm.math;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Bj_15649 { private static int n, m; public static void main(String[] args) throws IOException { input(); int[] output = new int[m]; boolean[] visited = new boolean[n]; permutation(n, m, 0, visited, output); } private static void permutation(int n, int m, int depth, boolean[] visited, int[] output) { if (depth == m) { printOutput(output); return; } for (int i = 0; i < n; i++) { if (!visited[i]) { visited[i] = true; output[depth] = i+1; permutation(n, m, depth+1, visited, output); visited[i] = false; } } } private static void printOutput(int[] output) { for (int o : output) { System.out.print(o + " "); } System.out.println(); } private static void input() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); }j
Java
복사