[알고리즘] 백준 2661 좋은수열 -백트래킹- 코틀린

 

 

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

2661번: 좋은수열

 

백준 2661 좋은수열이라는 백트래킹 유형 문제를 풀어봤습니다. ㅎㅎ

 

인접한 두 개의 부분 수열이 동일한게 없는게 좋은수열이며 이를 만족하는 가장 작은 수를 구하는 문제였습니다.

가장 중요한 부분은 check() 함수로 끝에서부터 1,2,3... 개로 양쪽으로 나눠 동일한 부분수열을 가졌는지 체크해줍니다.

 

 

풀이는 다음과 같습니다.

 

[Kotlin]

import java.util.*
import kotlin.system.exitProcess


lateinit var arr: IntArray
var n: Int = 0
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    n = sc.nextInt()
    arr = IntArray(n)
    dfs(0, "")
}

fun dfs(depth: Int, num: String) {
    if (depth == n) {
        println(num)
        exitProcess(0) // 가장 작은수 발견 종료
    }
    for (i in 1..3) {
        if (check(num + i)) {
            dfs(depth+1, num + i)
        }
    }
}

// 좋은 수열인지 검사
fun check(num: String): Boolean {
    for (i in 1..num.length / 2) {
        val left = num.substring(num.length - i * 2, num.length - i)
        val right = num.substring(num.length - i, num.length)
        if (left == right) return false
    }
    return true
}

https://github.com/mtjin/algorithm_practice/commit/75f71f413759e0c219ca9c5300d6c0f0ec2ab50d

백준 2661 풀이 · mtjin/algorithm_practice@75f71f4

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!