[백준 15651번] [Kotlin] N과 M (3)

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

15651번: N과 M (3)

 

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

 

 

설명

N과 M 시리즈. 3번째 문제입니다.

이번엔 중복을 허용하는 문제네요.

1번 소스 + 중복허용의 조합으로 풀면 될 것 같습니다.

 

 

소스코드

lateinit var arr: Array<Int>

var n = 0
var m = 0
val sb = StringBuilder()

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

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

    dfs(1, 0, "")
    print(sb.toString())
}

fun dfs(idx: Int, len: Int, str: String) {
    if (len == m) {
        sb.append(str).append("\n")
        return
    }

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

 

중복을 허용하지 않으므로 방문 여부를 체크하던 visited 배열이 빠졌습니다.

덕분에 n과 m 시리즈에서는 가장 간단한 백트래킹이 되었네요.

 

 

후기

다음 편에서 만나요.