백준 2661 좋은수열 Kotlin (백트래킹)

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

2661번: 좋은수열

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

알고리즘 분류

• 백트래킹

풀이

백트래킹 문제다.

전체적인 풀이는 다음과 같다.

1. n개의 자리에 1,2,3 중 하나의 수를 집어 넣는다.

2. 3^n의 가짓수로 시간 초과가 나기 때문에 가지치기를 한다.

3. n길이의 문자열이 완성됐다면 가장 작은 수를 출력한다.

 

이 문제의 핵심은 가지치기와 가장 작은 수 출력이다.

가지치기는 새로운 숫자를 넣을 때마다 만들어진 문자열의 길이의 반절만큼 양 쪽을 비교하여 나쁜 수열인지 확인한다.

문자열의 길이가 10이라면, 가장 오른쪽 숫자를 기준으로 길이 1만큼 비교, 2만큼 비교, ~~~ 5만큼 비교한다.

ex) 132121

2 == 1 different

21 == 21 same

132 == 121 different

2만큼 비교할 때 이미 두 숫자가 같으므로 나쁜 수열이다.

따라서 새로운 숫자를 넣을 때 이 숫자를 넣음으로써 나쁜 수열이 된다면 이 숫자는 넣지 않는다.(가지치기)

 

가장 작은 수 출력은, 한 자리에 넣을 수 있는 숫자는 1,2,3이다.

우리가 앞에서부터 숫자를 넣을 때 항상 1부터 검사한다면 재귀의 성질에 의해  n의 길이에 처음 다다랐을 때 가장 작은 수가 나온다.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

//무조건 1로 시작
//가장 작은 수
//1<= n<=80
//비교 함수
//백트래킹 가지치기 -> 비교 함수
//삽입 순서는 ? 123으로 하면 가능
var answer = ""
fun canAdd(result: StringBuilder) : Boolean {
    for(len in 1 .. result.length/2){
        var idx = result.length-len
        val ls = idx-len
        if(ls < 0) break
        val left = result.substring(ls,idx)
        val right = result.substring(idx,result.length)
//        println("$result $left $right ls : $ls idx : $idx")
        if(left==right) return false
    }
    return true
}

fun backTracking(n: Int, result: StringBuilder){
    if(answer.isNotEmpty()) return
    if(result.length == n){
        answer = result.toString()
        return
    }

    for(num in 1 .. 3){
        if(answer.isNotEmpty()) return
        result.append(num)
        if(canAdd(result)){
            backTracking(n, result)
        }
        result.deleteCharAt(result.lastIndex)
    }
}
fun main() = with(System.out.bufferedWriter()) {

    //input
    val n = getInt()
    //solve
    backTracking(n,StringBuilder())
    //output
    write(answer)
    close()
}