[백준] 2661. 좋은수열 (Kotlin)

문제

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

2661번: 좋은수열

 

풀이

0. 문제 해석

 

최솟값을 찾아야하므로 1,2,3 순서로 계속 넣어가면서 나쁜 수열일 경우 리턴한다.

길이가 n에 도달했는데 좋은 수열일 경우 그게 최솟값이다.

 

나쁜수열 판별을 위해 문자열 길이가 홀수/짝수만 신경써주면되는데 

 

예를들어 12345678 이 있으면 (예시이므로 123이 아닌 수도 넣음)

 

1234 5678
0~3/4~7

345 678
2~4/5~7

56 78
4~5/6~7

7 8
6 / 7  

 

위와같이 인접한 두개의 부분수열로 쪼갤 수 있고

 

 

1234567 이 있으면

234 567
1~3/4~6
45 67
3~4/5~6

6 7

5 / 6

 

으로 쪼갤 수 있다.

위 패턴으로 수열을 판별한다.

1. 전체 코드

// [백준] 2661. 좋은수열 (Kotlin)

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()

    solve("1")
    solve("2")
    solve("3")
}

fun solve(str: String){
    val len = str.length

    if(!check(str)){
        return
    }

    // 가장 작은 수열
    if(len == n){
        println(str)
        exitProcess(0)
    }

    // 다음에 같은 수가 나오면 안됨
    if(str[len - 1] != '1'){
        solve(str + '1')
    }
    if(str[len - 1] != '2'){
        solve(str + '2')
    }
    if(str[len - 1] != '3'){
        solve(str + '3')
    }
}

// 좋은 수열인지 판별
fun check(str: String) : Boolean{
    var count = (str.length + 1) / 2

    var start = 0
    var end = count

    // 홀수면 시작위치 조정
    if(str.length % 2 != 0){
        start = 1
    }

    // 수열 반반으로 나눠서 검사
    for(i in start until count){
        if(str.substring(start,end) == str.substring(end, str.length)){
            return false
        }
        start += 2
        end += 1
    }
    return true
}