글 읽기 - [Swift] DFS로 문제를 푸는데 도움 부탁드립니다.

whdvy3 2년 전 0

반례는 다 맞는거같은데 이상하게 16%에서 계속 틀리네요..

도움이 필요합니다 ㅠㅠ

let ns = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = ns[0]
let s = ns[1]

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var countDepth = 1
var visited = Array(repeating: false, count: 21)
var result = [Int]()
var count = 0
func dfs(_ depth: Int, _ start: Int){
    if depth == countDepth{
        var sum = 0
        for i in result{
            sum += i
        }
        if sum == s {
            count += 1
        }
        return
    }
    if start + 1 < n{
        while countDepth < n {
            for j in (start + 1)..<n{
                if !visited[j]{
                    visited[j] = true
                    result.append(arr[j])
                    dfs(depth + 1, start)
                    visited[j] = false
                    result.removeLast()
                }
            }
            countDepth += 1
        }
        
    }
}
for i in 0..<n{
    countDepth = 1
    visited[i] = true
    result.append(arr[i])
    if arr[i] == s {
        count += 1
    }
    dfs(0, i)
    result.removeAll()
}
print(count)

wapas 2년 전 4

반례입니다.

4 -6
2 -9 -2 -6
answer : 2
output : 1

4 -12
-6 3 -3 -3
answer : 1
output : 0

8 22
10 8 -6 6 0 10 5 3
answer : 6
output : 1

whdvy3 2년 전 1

코드가 난잡해서 다시풀다가 정답을 찾았습니다! 도움주셔서 감사드립니다.

let ns = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = ns[0]
let s = ns[1]

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var visited = Array(repeating: false, count: 21)

var cnt = 0
var sum = 0
func dfs(_ depth: Int, _ start: Int){
    if sum == s && depth >= 1{
        cnt += 1
    }
    
    for i in start..<n{
        if !visited[i]{
            visited[i] = true
            sum += arr[i]
            dfs(depth + 1, i)
            visited[i] = false
            sum -= arr[i]
        }
    }
}

dfs(0, 0)
print(cnt)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Swift] DFS로 문제를 푸는데 도움 부탁드립니다.

whdvy3 2년 전 0

wapas 2년 전 4

whdvy3 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말