[백준 15664번] [Kotlin] N과 M (10)

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

15664번: N과 M (10)

 

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

 

 

설명

N과 M 시리즈 10번째 문제입니다. 이제 이 시리즈도 얼마 남지 않았군요.

다들 예상하셨듯, 9번 문제에 2, 6번과 같 변형을 가한 문제입니다.

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer


lateinit var visited: Array<Boolean>
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()

    visited = Array(n + 1) { false }


    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 idx..n) {
        if (!visited[i] && temp != arr[i]) {
            visited[i] = true

            temp = arr[i]

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

            visited[i] = false
        }
    }
}

 

9번의 문제에서 2, 6번과 마찬가지로 for문의 시작부분을 바꾸면 됩니다.

 

 

 

후기

n과 m 시리즈 9~12는 1~8에 비해 난이도가 좀 올라간 느낌이네요.

머리속에서 이전의 문제들과 헷갈리고, 섞여 난리났던 것 같습니다.