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
'Problem-Solving > BOJ' 카테고리의 다른 글
[BOJ/백준][Silver1] 12852 : 1로 만들기 2 (C++) (0) | 2021.09.12 |
---|---|
[BOJ/백준][Silver1] 16953 : A → B (Kotlin) (0) | 2021.08.30 |
[BOJ/백준][Silver3] 15657 : N과 M (8) (Kotlin) (0) | 2021.08.15 |
[BOJ/백준][Gold5] 13172 : Σ (Kotlin) (0) | 2021.08.15 |
[BOJ/백준][Silver1] 11660 : 구간 합 구하기5 (Kotlin) (0) | 2021.08.15 |