백준 숌 사이 수열(1469)

 

백트래킹 문제를 풀어보았다 

복잡해서 시간이 오래걸렸다.

 

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

1469번: 숌 사이 수열

 

초기에는 가능한 종류를 만들어보려고 하였지만 시간초과 발생 할 것같아서

주어진 경우의 수에서 가능한 경우의 수를 찾는 방식으로 처리를 했다.

 

문제의 핵심은 현재 뽑은 원소의 값이 2개가 위치할 수있는가 예를들어 2라면 현재 위치 2 ? ? 2 해서 마지막 2가 놓일 수 있는가 핵심이다.

 

나의 로직에서는

depth + element + 1 < N * 2 && answer[depth] == null && answer[depth + element + 1] == null

 

이게 핵심이 되겠다

 

※ 로직은 맞아보이는데 한동안 계속 실패하길래 뭐가 문제였을까 고민했다.

처음에 원소를 String으로 받아 정렬 처리했는데 이게 순서의 문제가 발생한거 같다

원소를 Integer로 변경후 정렬후 첫 정답을 뽑으니 해결... 참 어렵다...

 

package backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * https://www.acmicpc.net/problem/1469
 */
public class Q1469 {

    public static int N;
    public static int[] elements;
    public static ArrayList<String> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        backtracking();
    }

    public static void backtracking() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        elements = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i=0 ; i < N; i++) elements[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(elements);

        dfs_back(0, new String[N * 2], new boolean[N]);
        System.out.println(list.size() == 0 ? "-1" : list.get(0));

    }

    public static void dfs_back(int depth, String[] answer, boolean[] visited) {
        if (N * 2 == depth) {
            list.add(String.join(" ", answer));
            return;
        }

        if (list.size() > 0) return;

        if (answer[depth] != null) {
            dfs_back(depth + 1, answer, visited);
            return;
        }

        for (int i=0; i < N ; i++) {
            if (!visited[i]) {
                int element = elements[i];
                if (depth + element + 1 < N * 2 && answer[depth] == null && answer[depth + element + 1] == null) {
                    visited[i] = true;
                    answer[depth] = answer[depth + element + 1] = String.valueOf(elements[i]);
                    dfs_back(depth + 1, answer, visited);
                    answer[depth] = answer[depth + element + 1] = null;
                    visited[i] = false;
                }
            }
        }
    }



}

 

결과