[백준 15656번] [Kotlin] N과 M (7)

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

15656번: N과 M (7)

 

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

 

 

1. 설명

이번엔 5번의 소스에 중복을 허용한 버전입니다.

 

 

2. 소스코드

      

      

      

    
    

      <code />
    
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

lateinit var arr: Array<Int>

var n = 0
var m = 0

val sb = StringBuilder()

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nm = br.readLine()!!.split(" ")
    n = nm[0].toInt()
    m = nm[1].toInt()

    val st = StringTokenizer(br.readLine(), " ")

    arr = Array(n + 1) { 0 }

    for (i in 1..n) {
        arr[i] = st.nextToken().toInt()
    }
    arr = arr.sortedArray()


    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로 방문 여부를 체크할 이유가 사라졌습니다.

따라서 5번에서 visited를 없애고 나머지는 동일합니다.

 

 

3. 후기

8번 문제에서 만나요.