[BOJ] 1469. 숌 사이 수열

https://www.acmicpc.net/problem/1469

1469번: 숌 사이 수열

풀이

풀다가 틀려서 다른 코드를 참고했다..

기존에 접근했던 방법은 만들 수 있는 모든 수열을 만들어 체크하는 것이었는데, 최대 길이가 20인 수열을 순열로 만드는건 20! 이기 때문에 시간초과가 나버렸다.

참고한 방법은 2*N 길이를 완성해가는 과정에서 조건을 만족하지 못하는 경우를 제거해나가는 방법이었다. 입력 수열 X를 오름차순으로 정렬하고, 현재 위치에서 숫자 i를 사용하지 않았다면 현재 위치 length와 length + X[i] + 1를 X[i]로 채우고 다음으로 넘어가는 것이다.

 

코드

import java.util.*;
import java.io.*;

public class boj_1469_숌사이수열 {

    static int N;
    static boolean success = false;
    static int[] X, S, ans;
    static boolean[] used;

    static void backTracking(int length) {
        if (length == 2 * N) {
            for (int i : ans) {
                System.out.print(i + " ");
            }
            success = true;
            System.exit(0);
        }

        if (ans[length] != -1) {
            backTracking(length + 1);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!used[i] && length + X[i] + 1 < N * 2 && ans[length] == -1 && ans[length + X[i] + 1] == -1) {
                used[i] = true;
                ans[length] = ans[length + X[i] + 1] = X[i];
                backTracking(length + 1);
                ans[length] = ans[length + X[i] + 1] = -1;
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        X = new int[N];
        used = new boolean[N];
        S = ans = new int[2 * N];
        Arrays.fill(ans, -1);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < X.length; i++) {
            X[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(X);

        backTracking(0);

        if (!success) {
            System.out.println(-1);
        }
    }
}