어느날 스코틀랜드의 수학자 듀들리 랭퍼드(C. Dudley Langford)는 그의 아들이 컬러블록을 가지고 놀고 있는 것을 보고 있었다. 그러던 중 랭퍼드는 그의 아들이 배열한 세쌍의 컬러블록 (빨강, 파랑, 초록)이 두개의 빨간 블록은 한 블록만큼, 두개의 파란 블록은 두 블록만큼, 두개의 초록 블록은 세 블록만큼 떨어져 있는 것을 알게 되었다. 곧 그는 두개의 노란 블록을 더하여, 총 네 쌍의 컬러블록이 위와 같은 규칙을 갖도록 배열하는데 성공했다. 랭퍼드는 곧바로 이 문제의 일반화에 대해 흥미를 갖게 되었고 이 문제를 1958년에 발표하였다. 위 문제를 수학적으로 설명하면 다음과 같다:
2n개의 숫자 1,1,2,2,…,n,n을 아래의 규칙이 성립하도록 배열할 수 있을까? 임의의 1≤k≤n에 대하여, k와 또 다른 k는 서로 정확히 k만큼 떨어져 있다
출처: https://jjycjnmath.tistory.com/371
백준에 설명되어 있는 것과 이론은 거의 비슷하다.
문제는 2 * n 길이의 수열이며, 두 개의 n 사이에는 정확하게 n개의 수가 있다고 했다.
그리고 그 밑에 x번째 수와 y번째 수는 같다는 조건이 있다고 했으니 y - x - 1을 해주면 해당 숫자를 알 수 있다.
왜 y - x - 1을 해주면 그 자리의 숫자를 알 수 있냐면
예제 입력 1로 예시를 들어 2 * 3(n) = 6길이의 수열이라고 했을 때, 1 2 3 1 2 3이라고 임의의 수열을 생각해보겠다.
문제 설명에서 두 개의 n 사이에는 정확하게 n개의 수가 있다고 했다.
그 말은 즉,
두 개의 1 사이에는 정확하게 1개의 수가 있어야 한다 => 1 2 1 ...
두 개의 2 사이에는 정확하게 2개의 수가 있어야 된다고 했다. => 2 1 1 2...
이런 식으로 사이에 들어가는 숫자로 그 수를 알 수 있다.
예제 입력 1에서 x와 y는 5(y) - 1(x) 이므로 = 4가 나온다. 하지만 자기 위치를 제외하고 생각해야 하기 때문에 1을 한번 더 빼준다. ex ) 1(여기서) 2 3 4 5(여기 사이의 수)
그리고 백트래킹을 해줄 것이다.
종료 조건은 num == n * 2 + 1이 같을 때
개수를 증가시켜주고 재귀에서 빠져나온다.
visited 변수를 이용해서 사용한 숫자를 체크해줬다.
arr 변수를 이용해서 수열을 완성하였다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int n, x, y;
static int[] arr;
static boolean[] visited;
static int cnt;
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());
arr = new int[25]; // n의 최대 12 * 2 = 24 + 1
visited = new boolean[13]; // n의 최대 12 + 1
cnt = 0;
arr[x] = arr[y] = y - x - 1; // 양쪽으로 해당 숫자 저장
visited[y - x - 1] = true; // 사용된 숫자 표시
dfs(1); // 재귀 시작
System.out.println(cnt);
}
static void dfs(int num) {
if (num == n * 2 + 1) { // 랭퍼드 수열의 길이만큼을 arr에 채우면
cnt++; // 개수를 증가시켜준다
return;
}
if (arr[num] == 0) { // 현재 아무 숫자도 저장되어 있지 않은 상태
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // 해당 숫자가 사용되지 않았다면
if (num + i + 1 <= 2 * n && arr[num + i + 1] == 0) { // num 개 뒤의 인덱스에도 저장이 안되어 있는지 확인
visited[i] = true;
arr[num] = arr[num + i + 1] = i;
dfs(num + 1); // 숫자를 증가 시킨 후 재귀
arr[num] = arr[num + i + 1] = 0; // 해당 숫자를 방문하기 전으로 돌아감
visited[i] = false; // 해당 숫자 방문하기 전으로 변경
}
}
}
}
else dfs(num + 1);
}
}
