[백준] 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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

문제 풀이

문제에서 요구하는 것은 주어진 수열에서 연속된 값들을 더했을 때의 최대값을 구하는 문제입니다.

 

먼저 몇 가지 상황을 생각 해보겠습니다.

이 수열에는 음수도 존재하기 때문에 일단 모든 값이 음수일 경우를 생각해 보겠습니다.

모든 값이 음수일 경우에는 수열 속에서 어떤 값을 더해도 점점 더 작아지기만 합니다.

따라서 수열의 최댓값만 포함하는 배열 즉 길이가 1인 배열이 답이 됩니다.

따라서 모든 값이 음수일 때는 수열의 최댓값을 답으로 내면 됩니다.

 

그렇다면 양수와 음수가 함께 있는 경우는 어떨까요?

만약 하나라도 양수가 있다면 어떤 경우에도 음수는 답이 될 수 없을 겁니다.

이유는 하나의 양수만 포함하는 경우가 어떠한 음수보다 무조건 클 테니까요!

즉 값을 더하다가... 음수가 나왔다! 하면 그건 답이 아닌 겁니다.

 

그럼 이제 최댓값을 기억할 방법만 찾으면 될 거 같습니다.

 

그럼 문제를 푸는 순서를 적어보자면...

 

가장 먼저 모든 값이 음수인지 확인하고, 음수라면 최대값을 반환합니다.

하나라도 양수가 있는 경우엔 연속된 값을 더해야 하므로 합계를 저장할 변수를 하나 만듭니다.

이 변수는 0으로 초기화해주시고요! 그리고 정답을 저장할 변수도 하나 만들어 0으로 초기화합니다.

수열의 처음부터 더해주며 현재 합계와 정답 변수의 값을 비교해가며 더 큰 값을 정답 변수에 저장합니다.

그러다가 현재 수열의 합이 음수가 된 순간 그 값은 정답이 절대로 될 수 없기 때문에 음수가 되도록 만든 수는 절대 정답에 포함되면 안 됩니다. 즉 이런 순간엔 수열이 끊어야 하기 때문에 합계를 0으로 초기화해줍니다.

이 과정을 반복해주시면 됩니다.

 

예로 주어진 입력으로 한 번 해보면..

 

10 -4 3 1 5 6 -35 12 21 -1

result = 0, sum = 0

 

수열과 지금까지의 정답을 저장할 result 변수, 지금 확인 중인 수열의 합을 저장할 sum 변수도 만들어줍니다.

양수가 하나 이상 있기 때문에 앞에서부터 더 해가 봅니다.

 

첫 번째

sum = 10

result = 10

 

두 번째

sum = 10 + (-4) = 6

result = 10 (10이 6보다 크기 때문에 유지)

 

세 번째

sum = 10 + (-4) + 3 = 9

result = 10

 

이렇게 진행하다가 이런  sum = 10 + (-4) + 3 + 1 + 5 + 6 = 21 인 순간 다음을 살펴보겠습니다.

다음에 위치한 -35를 더해버리면 sum = -14가 되어 음수가 되어버립니다.

즉 절대로 답이 될 수 없기 때문에 수열을 끊기 위해 sum 변수에 0을 다시 넣고 12부터 다시 더해줍니다.

그다음은 이렇게 됩니다.

 

12를 보는 루프

sum = 12

result = 21

 

21을 보는 루프

sum = 33

result = 33

 

-1을 보는 루프

sum = 32

result = 33

 

즉 이렇게 마지막 수 까지 보면 정답을 얻어낼 수 있습니다!

소스 코드

import Foundation

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 sum: Int = 0
    
    for i in numbers {
        sum += i
        // sum이 음수가 되면 수열을 끊어야 하므로 0으로 초기화
        if sum < 0 {
            sum = 0
        }
        // 매번 result값과 현재 sum 값을 비교해준다
        if result < sum {
            result = sum
        }
    }
    
    return result
}
print(solution())