[백준 15655번] [Kotlin] N과 M (6)

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

15655번: N과 M (6)

 

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

 

 

1. 설명

N과 M. 6번째 문제입니다.

이제 슬슬 레파토리를 파악하셨을 텐데요.

2~4번은 1번의 파생 문제였다가,

5번부터 변화구로 배열이 주어지고 이 배열로 백트래킹을 했다면,

이번엔 5번 + 2번 문제의 조합이네요.

주어진 숫자들로 오름차순으로 출력하는 문제입니다

 

 

2. 소스코드

      

      

      

    
    

      <code />
    
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
    }

    for (i in idx..n) {
        if (!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번의 소스에서 바뀐 점은 dfs안의 for문 입니다.

이전의 값보다 커야 하므로 i가 0부터 시작하는게 아니라, 바로 직전 index보다 커야 합니다.

 

 

3. 후기

7번째 문제도 슬슬 예상이 가실 텐데요.

6번이 5번 + 2번 조합이였으니,

7번이 5번 + 3번 조합이라 생각하셨다면,

정답입니다.

다음 장에서 만나요.