BOJ: #15657 - N과 M (8)

05:04

N과 M 시리즈를 차례대로 쭈욱 풀면서 점점 정답 비율이 높아지길래 왜 그런가 했더니, 사람들이 시리즈 순서대로 풀면서 유형을 파악해서 정답율이 늘었다는 걸 알았다. 왜냐면 내가 지금 그러고 있기 때문에…. 이제 약간 백트랙킹의 감이 잡힌다.

문제

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

내가 작성한 코드

Swift

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let m = input[1]
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()
var picked = [String]()
var result = ""
/*
 n: 전체 원소의 수
 toPick: 고를 수 있는 원소의 수
 */
func pick(n: Int, toPick: Int) {
    // 기저 사례: 고를 수 있는 원소의 수가 없으면 출력하고 종료
    if toPick == 0 {
        result += picked.joined(separator: " ") + "\n"
        return
    }
 
    // 수를 고른다. 같은 수를 여러 번 골라도 된다.
    for i in 0..<n {
        if let last = picked.last { // 비내림차순 확인
            if Int(last)! > nums[i] {
                continue
            }
        }
        picked.append(String(nums[i]))
        pick(n: n, toPick: toPick - 1)
        picked.removeLast()
    }
}
 
pick(n: n, toPick: m)
 
print(result, terminator: "")