15650번: N과 M (2)

문제 출처 : https://www.acmicpc.net/problem/15650

 

언어 : Kotlin

 

문제 설명 :

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

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

 

입력 :

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력 :

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
3 1	1 2 3
4 2	1 2 1 3 1 4 2 3 2 4 3 4
4 4	1 2 3 4

 

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

lateinit var arr: IntArray
lateinit var visited: BooleanArray

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = readLine().split(" ").map { it.toInt() }
    arr = IntArray(n + 1) { i -> i }
    visited = BooleanArray(n + 1)
    dfs(n, m, 1, 0, bw, "")

    bw.flush()
    bw.close()
}

fun dfs(n: Int, m: Int, idx: Int, depth: Int, bw: BufferedWriter, str: String) {
    if (depth == m) {
        bw.appendLine(str)
    }

    for (i in idx .. n) {
        if (!visited[i]) {
            visited[i] = true

            if (depth == 0) dfs(n, m, i, 1, bw, arr[i].toString())
            else dfs(n, m, i, depth + 1, bw, "$str ${arr[i]}")
            visited[i] = false
        }
    }
}