[백준 15666번] [Kotlin] N과 M (12)

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

15666번: N과 M (12)

 

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

 

 

1. 설명

N과 M 시리즈. 대망의 마지막 문제입니다.

9번의 소스에 10, 11번의 변형이 가해진 문제네요.

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer


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()
    

    dfs(1, 0, "")
    print(sb.toString())
}

fun dfs(idx: Int, len: Int, str: String) {
    if (len == m) {
        sb.append(str).append("\n")
        return
    }

    var temp = 0

    for (i in idx..n) {
        if (temp != arr[i]) {
            temp = arr[i]

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

dfs의 for문이 idx부터 시작하고,

중복을 허용하기 때문에 visited 배열이 제거된 모습입니다.

벌써 세 번째 반복이니, 다들 예상하셨을 거라 생각합니다.

 

 

3. 후기

꽤 긴 N과 M 시리즈가 끝났습니다.

문제마다 조금씩 변형을 가하면서, 미묘한 차이를 캐치하고 수정해나가는게 꽤나 머리를 아프게 했는데요.

백트래킹을 연습하기엔 굉장히 좋았던 문제였던 것 같네요.

여기까지 잘 푸신 분들이라면, 이제 백트래킹은 어느정도 감이 오실거라 생각합니다.

다음엔 다른 문제로 찾아뵙겠습니다.