백준 1912 파이썬 - 연속합 - 동적 계획법

백준 1912 파이썬

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

1912번: 연속합

 

10 -4 -3 1 5 6 -35 12 21 -1 = 33

2 1 -4 3 4 -4 6 5 -5 1 = 14

위의 예시와 같이 연속되는 합의 최대값을 구하는 문제이다.

 

이 문제에서 현재의 위치가 음수이고 이 음수를 이전까지의 연속된 합에 합했을 때 0보다 큰지 확인하는 것이 핵심이다. 합했는데 0보다 작은 경우.. 최대값이 이어갈 수 없다. 반대로... 합했는데 0보다 큰 수가 나오면... 최대 연속합이 될 확률이 아직 남아 있다는 것이다. 동적 계획법을 이용해서 풀 수 있고... 해당 문제는 굳이 배열이 아니라 변수에 값을 저장하면서 최대값을 구할 수도 있다. 둘의 속도에 큰 차이는 없다.

 

 

Python 풀이 1

배열을 이용한 동적 계획법으로 해결한 풀이이다.

import sys
read = sys.stdin.readline

N = int(read())
arr = [0] + list(map(int, read().split()))
cache = [-1001] * (N+1)

for n in range(1, N+1):
    cache[n] = max(arr[n], cache[n-1] + arr[n])
print(max(cache))

• 주어질 수 있는 수보다 작은 -1001을 캐시의 초기값으로 사용한다.
• 이전까지 연속 합에 현재 위치의 숫자를 더한 값과 현재 위치의 값 중 더 큰 값을 저장한다.
  • 현재 위치의 숫자가 양수인 경우 계속해서 더해나가고
  • 현재 위치의 숫자가 음수 인 경우... 이전 연속합에 더했을 때 음수가 나오면 다음 번에 양수가 나오든 음수가 나오든 무조건 arr[n]이 최대값이 된다. 연속합이 되는 수열을 초기화하는 효과를 볼 수 있다.
  • 현재 위치의 숫자가 음수 인 경우... 이전 연속합에 더했을 때 양수가 나오면 다음 번에 양수가 나오면 계속 연속합을 더해나가고 음수가 나오면 다시 경우의 수가 반복된다.

 

Python 풀이 2

사실상 풀이 1과 똑같은 작업을 하는거다. 단지 배열이 아니라 변수 2개를 이용했을 뿐이다.

import sys
read = sys.stdin.readline

N = int(read())
arr = list(map(int, read().split()))
max_sum = arr[0]
curr_sum = arr[0]

for n in range(1, N):
    temp = curr_sum + arr[n]
    curr_sum = temp if curr_sum > 0 and temp > 0 else arr[n]
    max_sum = curr_sum if curr_sum > max_sum else max_sum
print(max_sum)

• 최대 연속합을 저장하는 max_sum과 현재 연속합을 저장하는 curr_sum 변수를 사용한다.
• 현재 연속합이 양수이고 현재 연속합에서 현재 위치 값을 더했을 때 0보다 크면 더한 값을 반환하고 아니면 현재 위치 값을 연속합으로 지정한다.