백준 15650 N과 M(2)

백준 15650번 N과 M(2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

(1 ≤ M ≤ N ≤ 8)

접근방법

n-m의 인덱스까지만 실행하는 dfs 실행하여 만들 수 있는 수열의 종류를 얻었다.

코드

class IO15650 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun getNM() = br.readLine().split(" ").map { it.toInt() }
    fun write(message: String) = bw.write(message)
    fun close() = bw.close()
    fun flush() = bw.flush()
}

fun main() {
    val io = IO15650()
    val (n, m) = io.getNM()
    val ansSet = mutableListOf<String>()
    val visited = Array(n) { false }

    var cur = ""
    fun dfs(now: String, depth: Int, startNum: Int) {
        if (depth == m) {
            ansSet.add(now)
            return
        }
        for (idx in startNum..n) {
            if (!visited[idx-1]) {
                visited[idx-1] = true
                cur += idx.toString()
                dfs(cur, depth + 1, idx)
                cur = cur.substring(0, cur.lastIndex)
                visited[idx-1] = false
            }
        }
    }

    dfs("", 0, 1)

    ansSet.forEach { str ->
        var result = ""
        for (idx in (0..str.lastIndex)) {
            result += "${str[idx]} "
        }
        io.write(result.trim() + "\n")
    }
    io.flush()
    io.close()
}