백준 2661번: 좋은 수열 (Kotlin)

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

2661번: 좋은수열

안녕하세요, 이륙사입니다.

 

풀이

이번 문제는 백트래킹을 활용한 완전 탐색(brute force) 문제였습니다.

 

우선, 좋은 수열이란 무엇이고 나쁜 수열과 어떻게 구분지을 수 있을까요?

좋은 수열이란, 가장 끝자리부터 1자리, 2자리, 계속해서 인접 숫자들을 확인했을 때 같은 숫자가 없는 것을 말합니다.

 

그리고 이 과정을 통해 한 자리씩 추가해가면서 전체 수열을 만든다는 아이디어와 각 자리수를 만들 때마다 좋은/나쁜 수열을 판별해야겠다는 생각을 자연스럽게 떠올릴 수 있습니다. 어떤 수가 좋은 수열이라면, 그것의 부분 수열들도 모두 좋은 수열이어야 합니다. 

 

이 아이디어가 중요한 이유는 n자리를 만들고나서 좋은 수열인지 판별을 하면 3^80가지를 확인하기 때문입니다. 하지만 뒤에 자리수를 추가할 때마다 좋은 수열인지 확인한다면, 미리 불필요한 탐색의 가지수를 줄일 수 있기 때문에 훨씬 빠른 시간 안에 탐색이 가능합니다. 그리고 이처럼 불필요한 탐색을 사전에 줄이는 것이 백트래킹으로 전부 확인하는 방법의 핵심입니다.

백트래킹

 

생각 과정

1. 좋은 수열과 나쁜 수열이란 무엇이고 그 둘을 어떻게 구별할지 생각한다.
2. 그 과정에서 뒤에 한자리씩 추가하면서 전체 가지수를 확인하고, 숫자를 추가할 때마다 수열을 판별한다는 생각을 떠올린다.

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess

var n = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    n = readLine().toInt()
    findMinGood("")
}

fun findMinGood(number: String) {
    if (number.length == n){
        print(number)
        exitProcess(0)
    }

    for (i in 1..3){
        if (isGood(number + i)){
            findMinGood(number + i)
        }
    }
}

fun isGood(number: String): Boolean {
    val length = number.length
    for (i in 1..length / 2) {
        val left = number.substring(length - 2 * i , length - i)
        val right = number.substring(length - i ,length)
        if (left == right) return false
    }

    return true
}

/* 아래와 같이 비교할 수도 있습니다
fun isGood(number: String): Boolean {
    val length = number.length


    for (i in 1..length / 2) { // 비교 길이
        var isGood = false

        for (j in 0 until i) { // 자리수
            // 다른 숫자가 있다면
            if (number[(length - 1) - j] != number[(length - 1) - j - i]) {
                isGood = true
            }
        }

        if (isGood.not()) return false
    }

    return true
}

*/