백준 15918 랭퍼든 수열쟁이야!! Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/15918

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

문제

랭퍼드 수열은 다음 조건을 만족하는 길이 2n의 수열이다.

1. 1 이상 n 이하의 자연수가 각각 두 개씩 들어 있다.
2. 두 개의 1 사이에는 정확히 1개의 수가 있다.
3. 두 개의 2 사이에는 정확히 2개의 수가 있다.
4. ...
5. 두 개의 n 사이에는 정확히 n개의 수가 있다.

예를 들어 3, 1, 2, 1, 3, 2은 n=3인 랭퍼드 수열이다.

n이 주어졌을 때, 길이 2n의 랭퍼드 수열의 개수를 구하면 된다. 하지만 이렇게만 하면 재미가 없으니 조건 하나를 추가하고자 한다. x번째 수와 y번째 수는 같다는 조건이다. (이 번호는 1부터 시작한다.)

입력

세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n)

출력

x번째 수와 y번째 수가 같은 길이 2n의 랭퍼드 수열의 개수를 출력한다.

알고리즘 분류

• 백트래킹

풀이

백트래킹 문제이다.

가지 칠 조건을 알아보자.

1) 우선 x,y는 정해져 있다.

x번째, y번째 수가 같아야 하는데 두 개의 n 사이에는 n 개의 수가 있어야 하므로 x,y에는 y-x-1이 들어간다. (y는 x보다 항상 크다)

 

2) 1~n까지 수는 한 번씩만 사용해야 한다. (한 번씩은 한 쌍을 말한다.)

visited[1~n]을 두어 이미 사용했다면 다음 숫자로 넘어간다. (다음 인덱스가 아닌 1~n중 다음 숫자)

 

3) 두 개의 n 사이에는 n 개의 수가 있어야 한다.

현재 값을 넣을 곳이 idx고 넣을 값이 n이라면 idx+n+1은 2*n보다 작아야 한다.

또한, idx+n+1의 값은 비어있어야 한다.

 

4) 현재 값을 넣은 idx가 비어있지 않다면 다음 인덱스로 넘어간다.

 

5) 1~n개의 숫자를 모두 넣었다면 이를 카운트하고 종료한다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()
var answer = 0
fun backTracking(cnt: Int, idx: Int, n: Int, x: Int, y: Int, result: IntArray, visited: BooleanArray) {
    if (cnt == n) {
        answer++
        return
    }
    if (result[idx] != 0) {
        backTracking(cnt,idx + 1, n, x, y, result, visited)
    } else {
        for (i in 1..n) {
            if (visited[i]) continue
            if (idx + i + 1 >= 2 * n) continue
            if (result[idx + i + 1] != 0) continue
            visited[i] = true
            result[idx] = i
            result[idx + i + 1] = i
            backTracking(cnt+1,idx + 1, n, x, y, result, visited)
            result[idx] = 0
            result[idx + i + 1] = 0
            visited[i] = false
        }
    }
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    val (n, x, y) = getIntList()

	//solve
    val result = IntArray(2 * n)
    val visited = BooleanArray(n + 1)
    val num = y - x - 1
    result[x - 1] = num
    result[y - 1] = num
    visited[num] = true
    backTracking(1,0, n, x, y, result, visited)

	//output
    write("$answer")
    close()
}