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

요구능력 : DP에 대한 이해

 

코드설명 : 

 

이 문제는 연속합 문제를 선행학습 하고 오셔야 이해가됩니다.

 

문제의 핵심

1. 연속합

2. 수를 하나 제거할 수 있다.

3. 수를 제거하지 않을 수도있다.

 

이 문제는 연속합이기 때문에 연속적으로 합을 구해줘야 하는데 수를 하나 뺄수 있다.

중요한점은 꼭 왼쪽에서 부터 시작한다는 생각을 버려야 한다.

만약에 -35라는 수를 빼고 연속합을 구하고싶다면

-35를 기준으로 가장 왼쪽에있는값 10부터 6까지의 연속합과 가장오른쪽에 있는값 -1부터 12까지의 연속합을 구해주면 된다.

이렇게 하면 왼쪽부터 -35만빼고 연속합을 모두 고려할수 있는것이다.

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

 

n = 정수를 입력받는 부분

arr = n개의 정수로 이루어진 수열

dp_r = 오른쪽부터 시작하는 연속합

dp_l = 왼쪽부터 시작하는 연속합

result = 결과값인 연속합의 최대값을 저장

 

아래 코드는 왼쪽에서부터의 연속합을 구하면서 결과값에 큰 부분합을 저장해줌으로써 문제의 핵심3번을 해결한다.

for i in stride(from: 0, to: n, by: 1){
    if i >= 1{
        dp_l[i] = max(arr[i], dp_l[i - 1] + arr[i])
    }
    result = max(result, dp_l[i])
}

 

아래코드는 문제의 핵심2번을 해결한다.

수를 하나 제거하게될경우 제거된수의 인덱스를 k라고 했을 때

왼쪽연속합의 k-1번째까지 + 오른쪽연속합의 k+1까지

이렇게하면 빼고싶은 수를 제외하고의 연속합을 구할 수 있게되는것이다.

아래 else if문은 k + 1이 n과 같아지는 경우에 indexOutOfRange가 일어나기 때문에 처리해준것이다.

for k in stride(from: 2, to: n, by: 1){
    if k + 1 < n{
        result = max(result, dp_l[k - 1] + dp_r[k + 1])
    }else if k + 1 == n{
        result = max(result, dp_l[k - 1])
    }
    
}

 

 

후기 : 항상 느끼는건데 DP는 풀어도 풀어도 신박한방법이 많다.

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp_r = Array(repeating: 0, count: n)
var dp_l = Array(repeating: 0, count: n)
var result = Int.min
dp_l[0] = arr[0]
dp_r[n - 1] = arr.last!
for i in stride(from: 0, to: n, by: 1){
    if i >= 1{
        dp_l[i] = max(arr[i], dp_l[i - 1] + arr[i])
    }
    result = max(result, dp_l[i])
}

for j in stride(from: n - 2, through: 0, by: -1){
    dp_r[j] = max(arr[j], dp_r[j + 1] + arr[j])
}

for k in stride(from: 2, to: n, by: 1){
    if k + 1 < n{
        result = max(result, dp_l[k - 1] + dp_r[k + 1])
    }else if k + 1 == n{
        result = max(result, dp_l[k - 1])
    }
    
}
if n == 1 {
    print(arr[0])
}else {
    print(result)
}