알고리즘 문제
[백준] 15649번 N과 M (1)
feelcoding
2020. 1. 6. 14:21
728x90
단계별로 풀어보기 백트래킹의 1단계 문제
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
www.acmicpc.net
그냥 순열을 구하면 된다.
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++이 훨씬 빠르다. 정말 놀라울 정도로 차이가 난다.
728x90