하나씩 하나씩 백트래킹하면 시간초과가 난다.
단적이지만 예제를 보면 간단한 법칙이 보인다. (8,7)의 자리가 바뀌고, (5,4), (2,3)의 자리가 바뀐다.
앞부터 차례대로 -1,0,+1의 숫자가 사용되었는지 확인 후 swap하는 방식으로 하면 풀린다.
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 | #include <stdio.h> #include <algorithm> using namespace std; int n, t, a[50001]; bool c[50001], d[50001]; bool solve(int x) { if (x == n) return true; if (d[x]) return solve(x + 1); for (int i = -1; i < 2; i++) { if (!c[a[x] + i] && a[x] + i > 0) { int target = x; for (int j = x + 1; j < n; j++) if (a[j] == a[x] + i) { target = j; break; } c[a[x]] = c[a[target]] = 1; d[target] = 1; swap(a[x], a[target]); if (solve(x + 1)) return true; c[a[x]] = c[a[target]] = 0; swap(a[x], a[target]); d[target] = 0; } } return false; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); solve(0); for (int i = 0; i < n; i++) printf("%d\n", a[i]); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 5619 세 번째 (0) | 2017.10.30 |
|---|---|
| 3758 KCPC (0) | 2017.10.30 |
| 13226 Divisors Again (0) | 2017.10.30 |
| 14891 톱니바퀴 (0) | 2017.10.26 |
| 14890 경사로 (0) | 2017.10.26 |