fork download
copy 
  1. /*
  2. 최대한 오른쪽에 더 높은 숫자를 넣는 방법을 선택
  3. 불가능한 경우도 있음 dfs탐색?
  4. 16
  5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  6. 4 5 1 2 1 4 2 5 8 10 11 12 13 15 16 14 6 8 9 7 10 3 11 6 12 3 13 7 9 15 14 16
  7. ??
  8. 3
  9. 1 2 3
  10. 231213
  11.  */
  12. #include <algorithm>
  13. #include <iostream>
  14. using namespace std;
  15. int N, T;
  16. void print(int *arr) {
  17.     for (int i = 1; i <= 2 * N; i++) {
  18.         cout << arr[i] << ' ';
  19.     }
  20.     cout << '\n';
  21. }
  22.  
  23. // 주어진 수를 어디에 넣을지 고민하는게 아니라, 주어진 자리에 어떤 수를 넣을지 고민
  24. bool dfs(int *X, int *arr) {
  25.     int k = 0;
  26.     while (arr[++k] != -1)
  27.         ;
  28.     if (k > 2 * N) {
  29.         for (int i = 1; i <= 2 * N; i++) {
  30.             if (arr[i] == -1) {
  31.                 return false;
  32.             }
  33.         }
  34.         return true;
  35.     }
  36.     for (int i = 0; i < N; i++) {
  37.         int n = X[i];
  38.         if (n != -1 && k + n + 1 <= 2 * N && arr[k] == -1 && arr[k + n + 1] == -1) {
  39.             arr[k] = arr[k + n + 1] = n;
  40.             X[i] = -1;
  41.             // print(arr);
  42.             if (dfs(X, arr)) {
  43.                 return true;
  44.             }
  45.             arr[k] = arr[k + n + 1] = -1;
  46.             X[i] = n;
  47.         }
  48.     }
  49.     return false;
  50. }
  51.  
  52. int main() {
  53.     cin >> N;
  54.     int X[16];
  55.     for (int i = 0; i < N; i++) {
  56.         cin >> X[i];
  57.     }
  58.     sort(X, X + N);
  59.     int arr[33];
  60.     for (int i = 0; i <= 2 * N; i++) {
  61.         arr[i] = -1;
  62.     }
  63.     if (dfs(X, arr)) {
  64.         print(arr);
  65.         return 0;
  66.     }
  67.     cout << -1;
  68. }
  69.  
Success #stdin #stdout 0.19s 5312KB
comments (?)
stdin
copy 
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
stdout
copy 
1 2 1 3 2 4 8 3 12 13 4 10 14 15 16 8 9 6 11 5 7 12 10 13 6 5 9 14 7 15 11 16
https://ideone.com/jCj5za
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!