[BOJ/백준][Silver3] 15652 : N과 M (4) (Kotlin)

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

15652번: N과 M (4)

 

 

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

[풀이]
이전 포스팅의 "N과 M (2)" 문제와 비슷하게 접근하면 되지만 다른 점이 같은 수를 여러번 선택할 수 있다는 점입니다.

재귀함수 내 n을 선택했을때의 호출 부분을 아래와 같이 변경해주면 됩니다.
used[n]++
sol(n,k+1)
used[n]--
n을 또 선택할 수 있으므로 n을 그대로 인자로 넘기고, used를 true false가 아닌 n이 몇개 쓰였는지를 체크하기 위해
호출시 used[n]++을 해주고 리턴시 used[n]--를 해줍니다.
수열을 출력시에는 used[n]의 값만큼 n을 출력해주면 됩니다.

 

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var N=0
var M=0
var used = Array<Int>(9){0}
fun sol(n:Int,k:Int){
    if(k==M){
        for(i in 1..N){
            repeat(used[i]){
                print("$i ")
            }
        }
        println()
        return;
    }
    if(n>N) return;
    used[n]++
    sol(n,k+1)
    used[n]--
    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/15652.cpp