[백준(BOJ)] 1912 연속합 - 스위프트 (Swift)

[Silver II] 연속합 - 1912

문제 링크

성능 요약

메모리: 76112 KB, 시간: 32 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 1월 22일 00:35:22

문제 설명

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

풀이

해당 문제는 DP를 이용해서 풀어야하는 문제였습니다. 연속된 수 중에서 가장 큰 합을 구하기 위해선 우선 음수가 나타나면 안된다고 생각하였습니다. 특정 범위의 합이 음수라는 것은 굳이 해당 범위를 더할 이유가 없기 때문입니다.

 

하지만 해당 숫자가 음수가 나와도 전체 합이 음수가 되지 않을 수 있기 때문에, 해당 숫자를 포함하여 범위를 확장시키는 것과, 범위를 다시 조정하는 것 중 이득이 되는 방법으로 최대 합을 구하고자 하였습니다.

 

예시의 식을 보았을 때, 10부터 -35까지 더한 범위보다 12부터 범위를 다시 시작하는 것이 이득이기 때문에, 12부터 다시 범위를 지정하여 더하도록 하였습니다.

 

DP에서 가장 중요한 것은 이전의 계산을 다음 계산에 사용해야 한다는 점입니다. 따라서 dp[n]을 구할 때 dp[n-1]에서 n번째 수를 더한 값과, n번째 수부터 다시 시작하는 값을 비교하여 최대값을 dp[n]에 저장하도록 하였습니다.

 

다음은 코드입니다.

let n = Int(readLine()!)!
let integers = readLine()!.split(separator: " ").map { Int($0)! }
var dp = Array(repeating: 0, count: n)
dp[0] = integers[0] // 첫 번째 값
var count = 0

for i in 1..<dp.count {
    dp[i] = max(dp[i - 1] + integers[i], integers[i])
}

print(dp.max()!)