백준 1469 숌 사이 수열 Kotlin (백트래킹)

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

1469번: 숌 사이 수열

문제

숌은 N개의 다른 숫자로 구성되어 있는 집합 X를 만들었다. 그리고, 길이가 2N인 숌 사이 수열 (S)을 만들려고 한다.

숌 사이 수열이란 다음과 같다.

1. X에 들어있는 모든 수는 숌 사이 수열 S에 정확히 두 번 등장해야 한다.
2. X에 등장하는 수가 i라면, S에서 두 번 등장하는 i사이에는 수가 i개 등장해야 한다.

예를 들어, 숌이 만든 집합 X가 {1,2,3}이고, 숌이 만든 숌 사이 수열이 {2 3 1 2 1 3}이라면, 일단 X에 속하는 모든 수가 S에 두 번 등장하므로 1번 조건을 만족한다. 그리고, 2와 2사이엔 수가 두 개, 1과 1사이엔 1개, 3과 3사이엔 3개가 등장하므로 조건을 만족시킨다.

집합 X가 주어졌을 때, 숌 사이 수열 S를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 X의 크기 N이 주어진다. 둘째 줄에 X에 들어가는 수가 빈칸을 사이에 두고 주어진다. X의 크기는 8보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수이다.

출력

첫째 줄에 숌 사이 수열을 출력한다. 만약 여러 개일 경우 사전 순으로 가장 빠른 것을 출력한다. 만약 없을 경우에는 -1을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

숌 사이 수열의 첫 번째 칸부터 채워나가보자.

3

1 2 3

을 예로 들면

첫 번째 칸에 2를 넣었다 치자.

그럼 숌 사이 수열은 다음과 같다

2 _ _ 2

이제 두 번째 칸에 1을 넣었다 치자.

2 1 1 2

세 번째 칸, 네 번째 칸은 이미 숫자가 있으니 다섯 번째 칸에 3을 넣었다 치자

2 1 1 2 3 _ _ 3

N은 3이므로 우리가 원하는 수열의 길이는 6인데 이는 8로 정답이 될 수 없다.

그럼 다시 되돌아가서 두 번째 칸에 1 대신 3을 넣어보자.

2 3 _ 2 _ 3

세 번째 칸에 1을 넣어보자.

2 3 1 2 1 3

길이가 6인 숌 사이 수열이 완성되었다.

즉, 매 턴마다 X개의 숫자를 넣으면서 칸을 전진하고, 칸이 2*n에 도달하면 해당 집합이 숌 사이 수열인지 검사하여 맞다면 탐색을 종료한다.

답이 여러 개일 경우 사전 순으로 빠른 것을 출력하라고 했으니, 입력으로 주어진 X를 오름차순 정렬한 다음 순서대로 넣어보자.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()
var existAnswer = false
var answer = IntArray(100){-1}
fun main(){
    //input
    val n = getInt()
    val numbers = getIntList().sorted()
    //solve
    backTracking(0,n,numbers, BooleanArray(17))
    //output
    if(!existAnswer){
        print("-1")
    }
}

fun backTracking(idx: Int, n: Int, numbers: List<Int>, visited: BooleanArray) {
    if(existAnswer) return
    if(idx == 2*n){
        for(i in 0 until 2*n){
            if(answer[i] == -1) return
        }
        existAnswer = true
        print(answer.filter { it !=-1 }.joinToString(" "))
        return
    }
    if(answer[idx] != -1) {
        backTracking(idx+1, n, numbers, visited)
    }
    for(num in numbers){
        if(visited[num]) continue
        if(answer[idx] != -1 || answer[idx+num+1] != -1 ) continue
        answer[idx] = num
        answer[idx+num+1] = num
        visited[num] = true
        backTracking(idx+1, n, numbers, visited)
        visited[num] = false
        answer[idx] = -1
        answer[idx+num+1] = -1
    }
}