[백준/BOJ] 15654번: N과 M(5)

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

15654번: N과 M (5)

문제

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

• N개의 자연수 중에서 M개를 고른 수열

해설

N과 M(1) ~ (4)번을 풀었다면 이번 문제는 매우 쉽게 풀 수 있다.

 

앞의 문제들에서는 1부터 원하는 수만큼 수열을 만들었다.

이 문제에선 1부터 수열을 만드는 대신 우리가 미리 배열을 입력한 것으로 바뀐다.

따라서 우리가 미리 설정할 배열과 수열을 저장할 배열을 만들어 백트레킹을 하여 문제를 풀면 된다.

소스 코드

import java.lang.StringBuilder
import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    val sb = StringBuilder()
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()

    val arr = IntArray(n)
    st = StringTokenizer(readLine())
    for(i in 0 until n) arr[i] = st.nextToken().toInt()
    arr.sort()

    val saveNum = IntArray(m)
    val visit = BooleanArray(n)

    fun dfs(idx: Int) {
        if(idx == m) {
            saveNum.forEach { i -> sb.append("$i ") }
            sb.append("\n")
            return
        }
        for(i in 0 until n) {
            if(!visit[i]) {
                visit[i] = true
                saveNum[idx] = arr[i]
                dfs(idx + 1)
                visit[i] = false
            }
        }
    }

    dfs(0)
    println(sb.toString())
}