[BOJ/백준][Silver3] 15650 : N과 M (2) (Kotlin)

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

15650번: N과 M (2)

 

 

 

[난이도] Silver3
[유형] 백트래킹

[풀이]
N이 8이하이기 때문에 재귀함수를 이용한 백트래킹으로 순서대로 수열을 출력할 수 있습니다.

재귀함수 sol(n,k)는 현재 n을 선택할 차례이며 지금까지 k개의 수를 선택했다는 의미입니다.

함수 내부에서 n을 선택한 경우와
used[n]=true
sol(n+1,k+1) : n을 선택했으므로 k를 1 증가시키고 used flag를 체크해줍니다.
used[n]=false

선택한 경우
sol(n+1,k) : 선택하지 않았으므로 k를 증가시키지 않습니다.

두가지로 나눠서 재귀호출을 해주어 k가 M인 경우 M개를 선택한 것이므로 used가 체크된 원소들을 출력하면
모든 수열을 순서대로 구할 수 있습니다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var N=0
var M=0
var used = Array<Boolean>(9){false}
fun sol(n:Int,k:Int){
    if(k==M){
        for(i in 1..N){
            if(used[i]) print("$i ")
        }
        println()
        return;
    }
    if(n>N) return;
    used[n]=true
    sol(n+1,k+1)
    used[n]=false
    sol(n+1,k)
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var ip = readLine().split(' ').map{it.toInt()}
    N=ip[0]
    M=ip[1]
    sol(1,0)
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/15650.cpp