[Swift] 백준_연속합

문제

 

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

1912번: 연속합

 

 

풀이

 

전형적인 dp문제였던 것 같다.

 

다른 사람들의 풀이를 보면 내가 좀 복잡하게 푼 것 같긴하다.

 

우선 maxValue라는 변수를 이용해 원래 배열의 최대값을 구해준다.

그리고 cache라는 변수를 이용해 이름뜻대로 지금까지의 값을 담아주도록 하였다. 이때, 새로운 수인 numbers[i]와 더했을 때 0보다 작아지지않으면 계속해서 더해주도록 했다. 계속해서 result 변수에 지금까지의 cache와 원래의 result 값 중 최대값을 넣어주기 때문에 cache값이 작아지더라도 0보다만 크다면 계속 더해주도록 하였다. 

 

만약 값을 더하다가 0보다 작아지는 경우엔 이후에 어떤 수를 더해도 그 수보다 작을 것이므로 이때는 cache의 값을 바꿔줘야했다. 나는 여기서 maxValue가 0보다 작을 경우에는 maxValue로 해주었고 아닌 경우엔 0으로 잡아주었다. 만약 maxValue가 0보다 작은데 0으로 잡아버리면 max()에서 배열의 max값이 아닌 0으로 나올 수도 있기 때문이다.

import Foundation

let n = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var maxValue = numbers.max()!
var cache = numbers[0]
var result = maxValue
for i in 1..<n {
    if cache + numbers[i] < 0 {
        cache = maxValue < 0 ? maxValue : 0
    } else {
        cache += numbers[i]
    }
    result = max(result,cache)
}
print(result)

 

 

_____________________________________________________________________________________________________

 

잼잼