[Swift 알고리즘] 백준 13398 (연속합 2)

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

13398번: 연속합 2

 

문제

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

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

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

 

해결방법

https://maramincho.tistory.com/51

[Swift 알고리즘] 백준 1912 (연속합)

선행 연속합을 풀고 와야 함

요약 

왼쪽에서 만드는 DP와 오른쪽에서 만드는 DP값 reversDP값들을 만들어 비교하면 된다.

arr = [10, 30 -15, -30, 20, 50]이라고 가정DP=[10, 40, 25, -5, 20, 70] 전에 구했던 DP가  다음과 같다고 하자. 그렇게 되면 DP값들은 현재 점에서 만들 수 있는 최대 합 이라고 생각하자. 따라서 현재 점에서 만들 수 있는 최대값을 reversDP값을 구하여 왼쪽에서 오는 최대합과 오른쪽에서 오는 최대합을 비교하여 계산하면 된다.

 

 

 

생각했던 과정

우리는 연속합을 구하는 것을 생각해보자. 우리는 수를 읽을 때 왼쪽에서 오른쪽으로 읽는다. 연속합을 구할 때 이전까지의 값들을 활용할 지 활용하지 않을지를 고민했다. 이 아이디어에 착안하여 생각해보자. 앞쪽에서부터 DP를 활용하여 연속합을 구하자. 그러고 나서 어디서 한개를 제거해야 좋을까? 에 대답은 "끊어지는 부분"이다. 

예를 들어보자

arr = [10, 30, -45, 20, 50] 그러면 DP값을 구하면 DP= [10, 40, -5, 20, 70]이 된다. (DP[i] = max(DP[i], DP[i] + DP[i - 1])

앞쪽에서 가장 길게 이어진 부분은 [10, 30, -5], 뒤쪽에서 가장 길게 이어진 부분은 [20, 50] 이렇게 된다면 [-45]를 없애면 최대가 된다.

 

arr = [10, 30 -15, -30, 20, 50] DP값을 구하면 DP=[10, 40, 25, -5, 20, 70] 이다. 가장 길게 이어져 온 부분은 [10, 30, -15, -30], [20, 50]이다. 이렇게 생각하여, -30 을 계산한다. 우리는 직감적으로 "-30"을 빼면 최대가 되는 것을 알지만 모든 상황에서 직감적으로는 해결할 수 없다. 이를 해결하기 위해서 우리는 구한 DP의 연속합에 대해서 다시 생각해 볼 필요가 있다. DP값들은 현재 점에서 만들 수 있는 최대합의 값들의 집합이다.

즉 DP=[10, 40, 25, -5, 20, 70] 에서 DP[0] 은 arr[0] 을 활용하여 만든 DP의 최댓값이다. DP[3]은 arr[3]->(-30)을 활용하여 만든 최댓값이다.

 

arr = [10, 30 -15, -30, 20, 50] 의 DP값을 생각해보자

DP=[10, 40, 25, -5, 20, 70] 

DP=[10, 40, 25, -5, 20, 70] 

이렇게 두개로 나눌 수 있다. 

 

예제 하나를 더 구해보자 

arr = [10, 30, -70, 20, -30, 50, 60]

DP = [10, 40, -30, 20, -10, 50, 110]

DP = [10, 40, -30, 20, -10, 50, 110]

DP = [10, 40, -30, 20, -10, 50, 110]

이렇게 나뉘어지는 것을 확인할 수 있다. 계산하기 위해서 우리는 분기점마다 계산하는 방법이 있다. -30 ,-10 부분에서 계산 하는 방법을 취할 수 있다. 그러나 이렇게 계산하게 된다면 문제가 있다.

arr = [-1, -2, -3, -4] 일 경우 모든점이 분기여서 시간복잡도가 증가한다. 이를 해결하기 위한 최후의 방법은 모든 reversDP를 구하면 된다.

 

찐 해결과정

arr = [10, 30 -15, -30, 20, 50] 의 DP값을 생각해보자

DP=[10, 40, 25, -5, 20, 70]  뒤쪽부터 계산한다면 reverseDP = [65, 55, 25, 40, 70, 50]가 된다. DP[i]값들의 정의는 arr[i]을 활용하여 만든 연속합의 최대.이것을 계산함에 있어서 우리는 현재 인덱스를 제외하고 계산하면 된다. 예를 들어 i = 1일 경우 DP[0] + reversDP[2].

DP[i - 1]값은 현재 점을 제외한(arr[i]) 왼쪽부터 arr[i - 1]까지 점에서 만들 수 있는 최대값과, reversDP[i + 1] 은 오른쪽 부터 arr[i + 1] 을 활용하여 만들 수 있는 최대값 이다.

  이렇게 새로운 arr을 만들고 거기서 최대값을 구하면 된다. newArr[i] = DP[i - 1] + reversDP[i + 1]

func solsolsol13398() {
    let inputN = Int(readLine()!)!
    let inputArr = readLine()!.split(separator: " ").map{Int($0)!}
    if inputN == 1 {
        print(inputArr[0])
        return
    }
    var lDPArr = inputArr
    var rDPArr = inputArr

    for i in 1..<inputN {
        lDPArr[i] = max(lDPArr[i - 1] + lDPArr[i], lDPArr[i])
    }
    
    for j in stride(from: inputN - 2, to: 0 - 1, by: -1) {
        rDPArr[j] = max(rDPArr[j + 1] + rDPArr[j], rDPArr[j])
    }
    var maxVal:Int = Int.min
    for i in 1..<inputN - 1 {
        maxVal = max(maxVal, lDPArr[i - 1] + rDPArr[i + 1])
    }
    print(max(maxVal, rDPArr.max()!))
}
solsolsol13398()