[프로그래머스 Lv3] 연속 펄스 부분 수열의 합 - Swift

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

대표적인 DP유형 문제인데, Swift 풀이가 많이 없길래 업로드 합니다 !

처음에 dp 배열을 2개 만드는 아이디어를 떠올리지 못해서 친구의 도움을 받아 풀었다 ! 샤라웃 janechoi..

다음에 비슷한 문제 나오면 dp 배열을 2개로 나눠서 계산하는 방법을 활용해야겠다 :) 

 

func solution(_ sequence:[Int]) -> Int64 {
    
    // -1로 시작하는 배열
    var dp1 = Array(repeating: 0, count: sequence.count)
    
    // 1로 시작하는 배열
    var dp2 = Array(repeating: 0, count: sequence.count)
    
    var dpnum1 = [-1]
    var dpnum2 = [1]
    
    var num = 1
    
    for i in 1..<sequence.count {
        dpnum1.append(num)
        dpnum2.append(-num)
        num = -num
    }
    
    dp1[0] = dpnum1[0] * sequence[0]
    dp2[0] = dpnum2[0] * sequence[0]
    
    for i in 1..<sequence.count {
        dp1[i] = max(sequence[i]*dpnum1[i], dp1[i-1]+(sequence[i]*dpnum1[i]))
        dp2[i] = max(sequence[i]*dpnum2[i], dp2[i-1]+(sequence[i]*dpnum2[i]))
    }
    
    return Int64(max(dp1.max()!, dp2.max()!))
}

1) -1로 시작하는 배열과 1로 시작하는 배열을 각각 만들어준다.

2) dp 배열 또한 -1로 시작하는 최댓값을 저장할 배열과 1로 시작하는 최댓값을 저장할 배열을 만들어준다.

3) 점화식을 세워 최댓값을 갱신해준다.

여기서 점화식을 세울 때, (현재 값, 이전까지의 합 + 현재값)을 비교해줘야 연속 배열을 만들 수 있다.

 

처음에는 연속인 것을 생각하지 못하고 (이전까지의 합, 이전까지의 합 + 현재값)을 비교해주었는데,

그렇게 되면 현재 인덱스를 띄우고 다음으로 넘어가게 되기 때문에 연속 배열이라는 조건이 깨진다 !!

이 점에 유의해서 풀어야 한다 !