[BOJ/JAVA] 백준 15918번 : 랭퍼든 수열쟁이야!!

15918번: 랭퍼든 수열쟁이야!!

 

---

 

 

• 생각

 

x, y번째 수가 같다는 것은 x, y번째 수가 모두 y-x+1이라는 것을 의미해서 미리 탐색을 채워주고 시작합시다.

 

backtracking메소드에 index를 증가시키면서 index가 2n이라면 수열을 모두 채운 것이기 때문에 1을 증가시켜 줌. 만약, 인덱스가 아직 채워지지 않았다면, 아직 쓰이지 않은 수 중 삽입 가능한 수 채운 뒤 다음 인덱스부터 재귀적으로 탐색

 

 

• 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int[] array, check;
	static int n, x, y,count;

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

		n = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		y = Integer.parseInt(st.nextToken());
		count = 0;
		
		array = new int[25];
		check = new int[25];
		array[x] = array[y] = y - x - 1;
		check[y-x-1] = 1;
		
		BackTracking(1);
		System.out.println(count);
	}

	private static void BackTracking(int index) {
		if(index == 2*n){
			count++; return;
		}
		if(array[index]==0){
			for(int i=1; i<=n; i++){
				if(check[i] == 1) continue;
				if(index+i+1<=2*n && array[index+i+1] == 0){
					array[index] = array[index+i+1] = i;
					check[i] = 1;
					BackTracking(index+1);
					array[index] = array[index+i+1] = check[i] = 0;
				}
			}
		}
	  else BackTracking(index+1);
	}
}