[백준 15665번] [Kotlin] N과 M (11)

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

15665번: N과 M (11)

 

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

 

 

1. 설명

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

이번에도 9번의 소스에 약간의 변형을 가해 풀어보겠습니다.

 

 

2. 소스코드

      

      

      

    
    

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


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
    }

    var temp = 0

    for (i in 1..n) {
        if (temp != arr[i]) {
            temp = arr[i]

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

중복을 허용한다 했으니, 9번의 소스에서 visited 배열이 빠진 형태입니다.

 

 

3. 후기

다음이 N과 M 시리즈 마지막 문제입니다.

여기까지 오신 분들. 조금만 더 달려봅시다.