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

단계별로 풀어보기 백트래킹의 1단계 문제

15649번: N과 M (1)

그냥 순열을 구하면 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        boolean[] visited = new boolean[n];
        int[] result = new int[m];
        permutation(n, m, 0, visited, result);
    }

    static void permutation(int n, int m, int num, boolean[] visited, int[] result) {
        if (num == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[num] = i + 1;
                permutation(n, m, num + 1, visited, result);
                visited[i] = false;
            }
        }
    }
}

순열을 구하는 방법을 모른다면 어려웠을 문제지만 순열을 공부했기 때문에 쉽게 풀 수 있었다.

 

7개월 뒤 8월 16일에 어떠한 것도 보지 않고 다시 풀어보았다. 이번엔 C++로 풀어봤다.

#include <vector>
#include <iostream>
using namespace std;

int n, m;

void permutation(int num, vector<bool> visited, vector<int> result) {
	if (num == m) {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << " ";
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			result[num] = i;
			visited[i] = true;
			permutation(num + 1, visited, result);
			visited[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	vector<bool> visited(n + 1, false);
	vector<int> result(m);
	permutation(0, visited, result);
	system("pause");
	return 0;
}

역시 C++이 훨씬 빠르다. 정말 놀라울 정도로 차이가 난다.