15652번: N과 M (4)

문제 풀이 아이디어

dfs를 통해 모든 경우의 수를 찾는 N과 M 문제입니다. 이 문제는 비내림차순이라는 조건이 있는데요. now ~ N을 순환하면 자연스럽게 비내림차순을 구현할 수 있습니다.

코드

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

// 결과 저장 배열
var result = [Int]()

// dfs 구현
func dfs(_ now: Int) {
    // 탈출조건 (수열의 길이 == M)
    if result.count == M {
        print(result.map{ String($0) }.joined(separator: " "))
        return
    }
    
    // 반복문 (Range의 범위에 주의!)
    for i in now...N {
        result.append(i)
        dfs(i)
        _ = result.popLast()!
    }
}

dfs(1)