[백준] 1912번 연속합 [Swift]

문제 링크

1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

문제 풀이

문제를 살펴보던 중 우선 예외상황이 하나 생각났습니다.

입력된 모든 값이 음수일 경우엔 더할 때 마다 값이 작아지므로 최댓값이 정답이라는 점이었습니다.

우선 이 예외를 생각하고 문제를 다시 살펴보았습니다.

 

이 문제에는 음수도 존재하기 때문에 무작정 더하는 것이 답을 찾는 방법은 아닌 거 같았습니다.

그렇다고 음수를 무조건 제외한다고 답을 찾을 수 있지도 않았습니다.

 

그러다 생각한 방법이 어떤 수열의 합이 0보다 작아지는 경우 이 경우는 답이 아니라는 점입니다.

예를 들어보겠습니다.

1, 2, -4, 1, 2, -3, 4

위와 같이 수열이 있다고 해보겠습니다.

처음 1,2,-4를 선택하게 되면 합이 -1이 됩니다.

0보다 작아졌죠?

이런 경우 4 다음에 음수가 오든 엄청 큰 양수가 오든 1,2,-4를 포함한 배열은 합이 최대가 아니게 됩니다.

만약 4다음에 100이 왔다고 해도 -1 + 100 = 99 이므로 그냥 100을 혼자 선택하는 게 더 이득입니다.

 

즉 이렇게 수열의 합이 0보다 작아지면 거기까지의 합과 지금까지의 합 중 최대값을 알아내고 다음 수로 넘어가면 됩니다.

 

위의 예제에서는 1,2를 더한 3을 기억하고 넘어가게 되는거죠!

그러다 나중에 1,2,-3,4의 합이 4이기 때문에 답은 4가 됩니다.

 

이 문제는 풀어보고 나서 생각해보니 계속 앞의 값들을 기억하며 결과적으로는 숫자 배열을 한 번만 보기 때문에 다이나믹 프로그래밍이라고 할 수 있을 거 같습니다.

소스 코드

func solution() -> Int {
    let _ = Int(String(readLine()!))!
    let numbers = readLine()!.split(separator: " ").map({Int(String($0))!})
    
    // 만약 입력된 수 중 최대값이 음수라면 최대값이 정답!
    // 최대값이 음수이다 -> 입력된 모든 값이 음수이다!
    let maxValue = numbers.max()!
    if maxValue < 0 {
        return maxValue
    }
    
    var result: Int = 0
    var now: Int = 0
    
    for i in numbers {
        now += i
        if now < 0 {
            now = 0
        }
        if result < now {
            result = now
        }
    }
    
    return result
}
print(solution())