[백준 15652번] [Kotlin] N과 M (4)

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

15652번: N과 M (4)

 

난이도 : 실버 3
태그 : 백트래킹

 

 

설명

1번을 베이스로 2번, 3번에서 나왔던게 섞여있네요.

1번 + 중복허용 + 비내림차순 입니다.

 

비내림차순이라는 말을 보고, 이게 뭐지? 내림차순이 아니라는 것 같은데, 그럼 오름차순과 무슨 차이지? 생각했는데,

오름차순은 수가 항상 증가해야 하므로,

중복되는 숫자는 허용하지 않아 중복이 있을 경우는

비내림차순 이라는 용어를 사용한다고 하네요. 지식이 늘었습니다.

 

 

소스코드

lateinit var arr: Array<Int>

var n = 0
var m = 0

fun main() {
    val nm = readLine()!!.split(" ")
    m = nm[1].toInt()
    n = nm[0].toInt()

    arr = Array(n + 1) { i -> i }

    dfs(1, 0, "")
}

fun dfs(idx: Int, len: Int, str: String) {
    if (len == m) {
        println(str)
        return
    }

    for (i in idx..n) {
        if (len == 0)
            dfs(i, 1, arr[i].toString())
        else
            dfs(i, len + 1, "$str ${arr[i]}")
    }
}

 

이번에도 방문 여부를 체크할 필요가 없기에 (중복을 허용하기에) visited 배열이 빠졌습니다.

다만, 비내림차순 이므로 항상 이전 노드보다 같거나 커야 하므로,

바로 직전 노드의 idx부터 for문을 반복합니다.

 

 

후기

To be continued.