[백준] (Swift) 15651번 - N과 M(4) (feat. DFS, 백트래킹)

🟠 문제

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

15652번: N과 M (4)

🟠 내가 푼 풀이

N과 M문제 세트가... (8)까지 있었던것 같은데,,, 이틀 정도만 얼른 더 풀고 끝내야지,,, 재미가 없다 재미가!! 

이것은 N과 M(2)번과 가장 흡사하다. (2)번은 (1)번 기준으로 오름차순으로 된 수열들만 출력하는 것이었는데 (4)번은 (3)번에서 오름차순으로 이루어진 수열들만 출력하면 된다. ... 그대로 똑같은 풀이를 이용하고, 범위만 살짝 바꿔주고! start 라는 매개변수를 추가해줬다.

현재 i 보다 큰 수들만 취급할 수 있도록 매개변수로 전달해준 것이다! DFS가 어떻게 돌아가는지에 대한 자세한 풀이는 (1)번 풀이를 참고해보자.

🟠 정답코드

let NM = readLine()!.split(separator: " ").map{ Int($0)! }
let N = NM[0]
let M = NM[1]

var stack = [Int]()
var answer = ""

private func dfs(start: Int) {
    if stack.count == M {
        answer += stack.map{ String($0) }.joined(separator: " ")
        answer += "\n"
        return
    }

    for i in start..<N+1 {
        stack.append(i)
        dfs(start: i)
        stack.removeLast()
    }
}

dfs(start: 1)
print(answer)

 

🔖 N과 M 관련 문제들 자세한 풀이는 아래에서 보면된당

https://didu-story.tistory.com/371

[백준] (Swift) 15649번 - N과 M(1) (feat. DFS, 백트래킹)

https://didu-story.tistory.com/372

[백준] (Swift) 15650번 - N과 M(2) (feat. DFS, 백트래킹)

https://didu-story.tistory.com/374

[백준] (Swift) 15651번 - N과 M(3) (두번째 풀이) (feat. DFS, 백트래킹)