이것저것 개발 블로그

https://www.acmicpc.net/problem/15650

 
 
 
풀이)

import java.util.Scanner;

public class Main_BJ_15650_N과M2 {
    static int n;
    static boolean[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        visited = new boolean[n];

        permutation(0, 0, m);
    }//main
    private static void permutation(int cnt, int cur, int m){
        if(cnt == m){
            for(int i=0; i<n; i++){
                if(visited[i])
                    System.out.print(i+1 + " ");
            }
            System.out.println();
            return;
        }


        for(int i=cur; i<n; i++){
            if(visited[i])
                continue;

            visited[i] = true;
            permutation(cnt+1, i, m);
            visited[i] = false;
        }
    }//permutation
}

순열로 풀면 되는 문제다!
n, m은 전역으로 선언하면 더 편한데 어쩌다보니 그냥 m은 들고다니게 됐다.
 
visited라는 전역 boolean 배열을 이용해 수를 선택했는지 안 했는지 확인한다!
이때, 중복은 안 되므로 방문한 것은 건너뛰는 작업이 필요하다.
 
방문하지 않았다면, 방문처리를 해주고 몇 개의 수를 선택했는지(cnt + 1), 현재 위치는 어디인지(cur)를 표시해주고, 다시 재귀호출한다.
재귀가 끝났다면 방문처리를 다시 없애줘야 다음 수열을 고를 때 영향을 받지 않을 수 있다!
 
마지막으로 cnt가 m과 같다면 수를 모두 선택한 것이므로 방문처리된 수들을 출력해준다.
나는 0부터 시작하여 선택할때마다 넘겼으므로 m과 같으면 0~m-1개를 택했으므로 m개가 맞는데,
1부터 시작했다면 m+1로 재조정해야한다.
 
순열을 다시 생각해볼 수 있는 간단한 문제!