15657번: N과 M (8)

문제 풀이 아이디어

중복은 가능하지만 비오름차순의 조건이 있습니다. 이런 경우 입력 받은 숫자들을 오름차순으로 정렬하고 현재 index 부터 순회하면 자동으로 비오름차순으로 수열을 만들 수 있습니다. 중복이 가능하므로 dfs(i + 1)이 아니라 dfs(i)입니다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()

// 결과 저장 배열 & 문자열
var result = [String]()
var toPrint = ""

// dfs 구현
func dfs(_ index: Int) {
    if result.count == M {
        toPrint += result.joined(separator: " ") + "\n"
        return
    }
    
    // array를 정렬했으므로 현재 index부터 순회하면 자동으로 비오름차순
    for i in index..<N {
        result.append(String(array[i]))
        dfs(i)
        _ = result.removeLast()
    }
}

// 함수 실행 & 답 출력
dfs(0)
print(toPrint)