[BOJ][백트래킹][실2]][10819] 차이를 최대로
문제 링크
풀이
알고리즘
N자리 K진수를 적용해서 해결하는 문제입니다.
input은 입력받은 값의 배열입니다. input은 그대로 두고 0 ~ N-1을 백트래킹으로 모든 경우를 선택해주면 됩니다. 이 때 각각의 경우는 v에 담겨진 채로 사용됩니다. 코드로 보면 좀 더 쉽습니다.
배열을 사용한 정답 코드
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define MAX 20
using namespace std;
typedef long long ll;
int n = 0, k = 0; //N:배열의 길이 , K: 진수
int input[MAX];
int v[MAX];
bool visited[MAX];
int ans = 0;
bool check(int depth) {
// depth-2번째와 depth-1번째가 놓을 수 있는 위치인지 판단
// depth -1까지 위치가 정해진 상태
if (depth <= 1) return true;
// 가로가 겹치는 경우 : row마다 하나씩 선택한다는 조건으로 만족
// 세로가 겹치는 경우 : visited를 사용해서 한 행에서는 하나만 선택하는 조건으로 만족
// 대각선으로 겹치는 경우
int x2 = depth - 1;
int y2 = v[x2];
for (int i = depth - 2; i >= 0; i--) {
int x1 = i;
int y1 = v[x1];
if (abs(x2 - x1) == abs(y2 - y1)) return false;
}
return true;
}
void recur(int depth) {
if (!check(depth)) return;
if (depth == n) {
/*for (int i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << "\n";*/
ans++;
return;
}
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
v[depth] = i;
visited[i] = true;
recur(depth + 1);
visited[i] = false;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
recur(0);
cout << ans << "\n";
return 0;
}
Success Notice: N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.
Leave a comment