[Swift] BOJ 1912 연속합

BOJ 1912 연속합

 

✅ 연속합은 스스로 빠르게 풀었다.

알고리즘에 매우 근접했으나, 다만 몇몇 예외 케이스를 제대로 확인하지 못해서 틀렸었다.

백준의 반례를 찾아 해결하긴 했으나, 이 부분까지 혼자 커버 가능하다면 더욱 좋을 것 같다.

 

[반례]

10

15 40 80 84 -22 -28 72 80 69 -44

answer : 390

 

3

-1 -4 5

answer : 5

 

🟠 문제 접근법

이것도 종이에 쓰면서 푸니까 쉽게 패턴을 찾을 수 있었다.

i번째 순서에서 dp[i-1]과 list[i-1]에서의 값을 비교해서 더 큰 값을 고른다. (value)

value와 현재 값을 비교해서 현재값이 value보다 크다면 내가 연속합이 최선임으로 dp[i]에 현재값을 넣는다.

근데 여기서 하나 주의할게 있는데, 만약 내가 더 크더라도 value가 양수라면 value를 현재값과 더해서 넣는게 무조건 더 최선의 결과이므로 value가 양수인지 체크한다.

그렇다면 왜 이게 가능한 것일까 한다면, 내 이전에 dp값이 항상 최선이라는 보장이 되기 때문인데, 그 이유는 내가 앞부터 계속 최선의 값을 골라 왔기 때문이다.

 

 

✅ 코드

        let input: Int = Int(readLine()!)!
        let list: [Int] = readLine()!.components(separatedBy: " ").map { Int($0)! }
        var dp = [Int](repeating: 0, count: input)
        
        dp[0] = list[0]
        
        if input >= 2 {
            dp[1] = max(dp[0]+list[1], list[1])
            
            for i in 2..<input {
                let value = max(dp[i-1],list[i-1])
                
                if value > list[i] || value > 0 {
                    dp[i] = list[i] + value
                } else {
                    dp[i] = list[i]
                }
            }
        }
        
        print(dp.max()!)