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

 

15663번: N과 M (9)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

 

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

[풀이]
별도의 정수 인자를 전달하지 않고 string을 전달하는 방식의 백트래킹으로 해결하였습니다.
중복을 피하기 위해 string 타입을 저장하는 set을 이용하였습니다.

 

import java.util.*
import kotlin.collections.HashSet
val bw = System.`out`.bufferedWriter()
val st = HashSet<String>()
var N=0;
var M=0
lateinit var arr : List<Int>
lateinit var used : BooleanArray
fun sol(str:String){
    if(str.filter { it=='#' }.length  == M) {
        var ret = str.replace('#', ' ')
        if(!st.contains(ret)) {
            st.add(ret)
            bw.write(ret+'\n')
        }
        return;
    }
    for(i in 0 until N){
        if(!used[i]){
            used[i]=true
            sol(str+arr[i].toString()+"#")
            used[i]=false;
        }
    }
}
fun main() = with(System.`in`.bufferedReader()){
    var ip = readLine().split(' ').map{it.toInt()}
    N=ip[0]; M=ip[1]
    arr = readLine().split(' ').map { it.toInt() }
    used = BooleanArray(N)
    arr = arr.sorted()
    sol("")
    bw.close()
}


https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/15663.kt

+ Recent posts