수레 움직이기
문제 설명
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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과 -1 또는 -1과 1이 번갈아 나오는 수열이다.
아래와 같이 수열이 주어졌을 때 [3, -6, 1] 에 펄스 수열 [1, -1, 1] 을 곱하면 [3, 6, 1] 이 된다. 이를 다 더하면 10 이 된다. 이게 최대값인데 이를 구하는 것이 문제이다.
문제 해결 과정
각 수열 위치에서 가장 큰 값을 구하면 된다. 즉 DP 로 풀면 된다. 그렇다면 어떤 값을 DP 로 구해야할지 생각해보자.
펄스 수열로 현재 값에 1 또는 -1 을 곱해지게 된다. 즉 경우의 수는 2가지가 된다. 현재 값이 양수와 음수일 때 최대 값을 구하면서 진행하면 된다. 조건이라면 현재 이전의 값을 현재 값과 더했을 때 현재 값보다 작으면 현재 값을 선택해야한다.
이를 시각화로 나타내면 아래와 같다.
첫 번째 값은 2 또는 -2 뿐이다.
두 번째 값부터는 이전 값을 가지고 계산을 해야한다. 화살표처럼 값을 계산해야한다. 현재 값이 + 일 때는 이전의 - 값을 더해야하는 것이기 때문이다. - 일 때는 이전의 + 값을 더해야한다.
계산한 값이 현재 값보다 작다면 현재 값을 선택하면 된다.
위 작업을 반복해서 진행하면 된다.
-7 과 -6이 나오는데 이 경우 현재 값인 -6을 선택하면 된다.
4번 째 값을 계산하면 문제 시각화 했을 때의 답이 나오게 된다.
끝까지 계산하면 아래와 같이 정보가 나오게 된다. 이 중에서 가장 큰 값을 선택하면 된다.
전체 코드
def solution(sequence):
dp = [[0, 0] for _ in range(len(sequence))]
dp[0] = [sequence[0], sequence[0] * -1]
for i, seq in enumerate(sequence):
if i == 0:
continue
value1, value2 = dp[i - 1][1] + (seq * 1), dp[i - 1][0] + (seq * -1)
dp[i] = [seq if value1 < seq else value1,
seq * -1 if value2 < seq * -1 else value2]
print(dp)
return max(map(max, dp))
print(solution([2, 3, -6, 1, 3, -1, 2, 4]), 10)
