[Swift][DP] 백준 5557번 (1학년)

요구능력

DP(메모이제이션)

 

문제설명

이론적으로 설명을 아주 잘 정리 해놓으신 분이 계신데 추천드립니다.

https://everenew.tistory.com/34

[백준] No.5557 - 1 학년 (C++)

 

후기

DP는 많이 풀어보는게 답이고, 다양한 풀이법을 계속해서 반복해야한다.

코드

let n = Int(String(readLine()!))!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: Array(repeating: 0, count: 901), count: 101)
dp[0][arr[0]] = 1

for i in 1..<n{
    for j in 0...20{
        if dp[i - 1][j] > 0{
            if j - arr[i] >= 0{
                dp[i][j - arr[i]] += dp[i - 1][j]
            }
            if j + arr[i] <= 20 {
                dp[i][j + arr[i]] += dp[i - 1][j]
            }
            
           
        }
    }
}
print(dp[n - 2][arr[n - 1]])