[백준] (Swift) 1912번 - 연속합 (가장 기초적인 DP 문제)

🟠 문제 링크

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

1912번: 연속합

 

🟠 문제 풀이 아이디어

가장 기초적인 dp문제로 이미 풀어봤던 문제라 어렵게 생각하지 않았다.

dp 에는 현재위치의idx-1 까지의 합과 해당 arr[idx] 값을 비교해본 후 최대값을 넣어준다. 앞에서부터 차례대로 차곡차곡 더해진 값에 현재값을 더하는게 더 큰지, 현재값만 바라보는게 더 큰지 확인하는 것이다! 

 

🟠 전체 소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1912_%EC%97%B0%EC%86%8D%ED%95%A9/main.swift

GitHub - deslog/Algorithm

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
var dp = Array(repeating: -9999, count: 100001) // 최소값 0으로 하면 안돼!!!!!
dp[0] = arr[0]

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

print(dp.max()!)