[Swift][DP] 백준 1912번 (연속합)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

이 문제에서 만들어 놓은 함정에 빠지고 문제를 풀 수 없었다..

함정은 바로 음수를 빼는 조건을 거는것이다.

음수포함해서도 연속값이 큰값이 나올 수 있다.

만약 음수를 빼는 조건을 거셨다면, 2번째 예제에서 14가 안나올것이다.

 

일단, 이 문제는 문제이름대로 dp에 연속적으로 합을 누적시킨다고 생각하면 된다.

dp[0] = arr[0] 을 해준 이유는 dp[0]에는 arr[0]만 누적된거다.

dp[1] = max(arr[1], dp[0] + arr[1])

dp[2] = max(arr[2], dp[1] + arr[2])

.

.

이런식으로 값을 계속해서 누적 시킨다.

max를 쓰는 이유는 값의 누적이 쓸모없어졌을 순간, 바로 현재 값이 이전에 (누적된 값 + 현재값) 보다 큰 순간에 현재값으로 바꿔주기 위함이다.

 

후기 : 쉽지않은 문제였다..

살짝 꼬인 DP느낌..

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: -1001, count: 100001)

dp[0] = arr[0]

for i in 1..<n{
    dp[i] = max(arr[i],dp[i - 1] + arr[i])
}
print(dp.max()!)