[Gold4-JAVA] 백준 15918 - 랭퍼든 수열쟁이야!!

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

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

 

 

🤔 문제 풀이

수열에 대한 규칙을 알려줬지만 처음에 수열을 어떻게 채워나갈지 막막했다.

하지만 문제에서 주어지는 입력 값 중 수열의 X와 Y위치의 숫자가 같다는 정보를 캐치했고

X와 Y의 숫자가 같으려면 X와 Y 사이의 간격이 X or Y와 같아야 함을 깨달았다.

 

ex) x = 4, y = 10 이라고 주어지면 x와 y 사이엔 5칸의 빈칸이 존재하고 이는 수열 규칙에 의해

x와 y가 5임을 알 수 있는 부분이다. 

이는 수열을 담은 배열 seq[x] = seq[y] = y-x-1 로 표현할 수 있다.

 

전체 수열 중 2칸의 빈칸을 채우고 이후부터는 완전 탐색을 통해 각 자리에 숫자를 입력할 수 있는지

확인하며 수열을 전부 채운 경우 answer + 1을 해주었다. 또한 수열에서 같은 숫자는 2번밖에 나오지

못하기 때문에 이미 등장한 숫자는 visit 처리를 해주었다.

 

🚨CODE

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
	static int n,x,y;
	static int answer = 0;
	static int[] seq;
	static boolean[] visit;
	public static void main(String[] args) throws IOException {
		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());
		
		seq = new int[2*n+1];
		visit = new boolean[2*n+1];
		seq[x] = seq[y] = y - x - 1;
		visit[seq[x]] = true; 
			
		solve(1);
		System.out.println(answer);
		
	}
	public static void solve(int idx) {
		 if(idx == 2*n) {
			 answer++;
			 return;
		 }
		
		if(seq[idx] == 0) {
			for(int i = 1; i<=n; i++) {
				if(visit[i])
					continue;
				if(idx+i+1 <= 2*n && seq[idx+i+1] == 0) {
					seq[idx] = seq[idx+i+1] = i;
					visit[i] = true;
					solve(idx+1);
					seq[idx] = seq[idx+i+1] = 0;
					visit[i] = false;
				}
			}
		}else
			solve(idx+1);
		
	}
}