[백준 15657번] [Kotlin] N과 M (8)

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

15657번: N과 M (8)

 

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

 

 

설명

5번의 소스에 중복을 허용한 비내림차순을 출력하는 문제입니다.

여기서 비내림차순이란,

오름차순은 항상 수가 증가하여야만 하므로 중복을 허용하지 않기 때문에,

중복이 있으면서 증가하는 수열의 경우, 비오름차순이라는 용어를 사용한다고 합니다.

 

 

 

소스코드

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) {
        println(str)
        return
    }

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

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

            visited[i] = false
        }
    }
}

 

5번의 소스에 4번의 응용 혹은 5번의 소스에 6, 7번 응용을 첨가해 풀이할 수 있습니다.

5번의 소스에서 중복을 허용하므로 visited 배열이 빠졌고, 비내림차순이여야 하므로

dfs의 for문이 idx부터 시작하여야 합니다.

 

 

 

후기

4개씩 세트로 문제가 나오네요. 9번 문제 부터는 또 다른 변화구가 날아올 것 같습니다.