[백준/BOJ] 5568번: 카드 놓기

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

5568번: 카드 놓기

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

해설

우선 카드를 뽑았을 때 모든 경우의 수를 찾아볼 것이다.

여기서 Set을 이용하여 중복된 값이 들어와도 입력이 되지 않도록 해준다.

visited라는 boolean 배열을 만들어 초기값을 false로 지정해준 후,

카드를 뽑았을 때 그 위치가 false라면 재귀함수를 통해 그 다음 번호를 뽑는 것을 반복한다.

카드를 원하는 개수만큼 뽑았다면 함수를 나와 뽑은 위치를 다시 false로 바꿔준다.

소스 코드

val set = HashSet<String>()
val n = readLine()!!.toInt()
val visited = Array(n+1) { false }
val card = Array(n+1) { "" }
val k = readLine()!!.toInt()

fun main() {
    for(i in 0 until n) card[i] = readLine()!!
    cardCombinate(k, 0, "")
    println(set.size)
}

fun cardCombinate(k: Int, idx: Int, num: String) {
    if(k == 0){
        set.add(num)
        return
    }
    if(idx > n) return
    for(i in 0 until n) {
        if(!visited[i]) {
            visited[i] = true
            cardCombinate(k-1, i, num + card[i])
            visited[i] = false
        }
    }
}