[Swift] 백준_N과 M(3)(15651)

문제

 

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

15651번: N과 M (3)

 

 

풀이

 

시간초과가 나와서 놀랬다. 기존에 arr로 만들어서 문자열로 다시 변경한 뒤 출력하는 과정때문인 것 같아서 바로 문자열로 만들어서 출력하도록하였따.

 

이전 문제들에서 배열로 받던 arr를 current라는 문자열로 바꾼 뒤, 반복문의 i를 이용해서 문자열 뒤에 더해주는 식으로 구현했다.

 

아무튼 이번 문제에서는 input[1]만큼 수를 출력해주는 것은 같지만 중복이 허용되므로 check같은 변수없이 모든 경우에서 반복문을 1부터 input[0]까지 돌려주었다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }

func dfs(_ current: String, _ depth: Int) {
    if depth == input[1] {
        print(current)
        return
    }
    for i in 1...input[0] {
        dfs(current + "\(i) ", depth + 1)
    }
}
dfs("", 0)

 

 

____________________________________________________________________________________________________

 

물론 기본적인 쉬운 문제지만 백트래킹이라는 것이 어떤 느낌인지 조금 알 것 같음. 근데 맞는지모름