Programmers / 연속 펄스 부분 수열의 합 - 부분합 DP / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 연속 펄스 부분 수열의 합 - (3단계) 부분합 DP

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

---

입출력 예sequenceresult

[2, 3, -6, 1, 3, -1, 2, 4]

10

---

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

---

나의 풀이

 

[-1,1,-1,1 ..] 과 [1,-1,1,-1 ..] 처럼 펄스를 곱해주기 위해 리스트를 만든다.

a = [0]
b = [0]
for i in range(len(sequence)):
    if i % 2 == 0:
        a.append(sequence[i])
        b.append((-1)*sequence[i])
    else:
        b.append(sequence[i])
        a.append((-1)*sequence[i])

처음에 두 리스트에 0을 넣어준 이유는 dp의 부분합을 이용하기 위해서 넣은 것이다.

 

연속 수열의 합을 구하는 내용이므로 dp의 부분합을 진짜 조금 다르게 해석한것이다.

 

다음과 같은 dp 함수를 만든다.

def dp(a):
    for i in range(1,len(a)):
        if a[i] + a[i-1] > a[i]:
            a[i] += a[i-1]
    return a

range(1,len(a)) 을 보면 1부터 시작하는데, 이전 값이 현재와 더했을때 더 큰 값이라면 해당 값을 더해나간다.

결국 출력값은 최대값이므로 다음 값으로 넘어가면서 더 큰값이 아니면 해당 값은 그냥 넘어감

 

그래서 최종적으로 가장 큰 부분수열의 합을 구할 수 있당

 

def solution(sequence):
    answer = 0
    a = [0]
    b = [0]
    for i in range(len(sequence)):
        if i % 2 == 0:
            a.append(sequence[i])
            b.append((-1)*sequence[i])
        else:
            b.append(sequence[i])
            a.append((-1)*sequence[i])
    def dp(a):
        for i in range(1,len(a)):
            if a[i] + a[i-1] > a[i]:
                a[i] += a[i-1]
        return a
    
    return max(max(dp(a)),max(dp(b)))

 

---

※ 알아야 할 것

- dp 부분합을 이용하였다.