반응형
문제
https://www.acmicpc.net/problem/15651
풀이
다음 순서로 문제를 해결한다
1. 만들 수 있는 모든 수열을 구해야 하므로, 완전 탐색을 이용한다
2. 수열의 길이는 m이고 중복되지 않게 오름차순으로 출력한다
재귀함수를 이용해 백트래킹 알고리즘으로 문제를 해결한다
코드
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def backtracking(depth):
if depth == m:
print(*answer)
return
for i in range(1, n + 1):
answer.append(i)
backtracking(depth + 1)
answer.pop()
answer = []
n, m = map(int, input().split())
backtracking(0)
|
cs |
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import java.util.Scanner;
public class Main {
private static int n, m;
private static int[] a;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
input();
solve();
}
private static void solve() {
rec(1);
System.out.println(sb.toString());
}
private static void rec(int count) {
if (count == m + 1) {
for (int i = 1; i<=m; i++) {
sb.append(a[i]).append(' ');
}
sb.append('\n');
} else {
for (int i = 1; i<=n; i++) {
a[count] = i;
rec(count + 1);
a[count] = 0;
}
}
}
private static void input() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
a = new int[m + 1];
sc.close();
}
}
|
cs |
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <bits/stdc++.h>
using namespace std;
int arr[9];
bool visit[9];
int N, M;
void solve(int cnt)
{
if (cnt == M)
{
for (int i=0; i<M; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
for (int i=1; i<=N; i++)
{
arr[cnt] = i;
solve(cnt + 1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
solve(0);
return 0;
}
|
cs |
반응형
'BOJ' 카테고리의 다른 글
BOJ 2178 - 미로 탐색 (0) | 2024.09.15 |
---|---|
BOJ 15649 - N과 M (1) (0) | 2024.09.12 |
BOJ 1018 - 체스판 다시 칠하기 (0) | 2024.08.24 |
BOJ 10872 - 팩토리얼 (0) | 2024.08.14 |
BOJ 1715 - 카드 정렬하기 (0) | 2024.08.06 |