[백준][KOTLIN][15652] N과 M(4)

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

15652번: N과 M (4)

문제 풀이

1. dfs 를 이용하여 주어진 입력 N, M 에 대해서 탐색한다.

2. 이때 숫자를 중복해서 사용해도 되기 때문에 visit 배열을 사용하지 않는다.

3. 비내림차순순열이어야 하기 때문에 현재 arr 의 마지막 값이 탐색하는 index 보다 작거나 같으면 arr 에 값을 넣고 dfs 를 수행하고 크면 dfs 를 수행하지 않고 다음 index 를 탐색한다.

4. M 과 depth 의 값이 같을 때 arr 를 출력한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    dfs(N, M, 0, mutableListOf())
}

private fun dfs(N: Int, M: Int, depth: Int, arr: MutableList<Int>) {
    if (M == depth) {
        for (a in arr) {
            print("$a ")
        }
        println()
        return
    }

    for (i in 1..N) {
        if (arr.isEmpty()) {
            arr.add(i)
        } else {
            if (arr.last() <= i) {
                arr.add(i)
            } else {
                continue
            }
        }
        dfs(N, M, depth + 1, arr)
        if (arr.isNotEmpty()) arr.removeLast()
    }
}