[백준] 1912 연속합 (Python 파이썬)

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

1912번: 연속합

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

---

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 최댓값을 찾는 문제이다.

 

DP라는 리스트(배열)의 각 칸에는 그 칸까지 숫자들을 고려했을 때의 연속합의 최댓값을 담을 것이다.

예를 들어, DP[2]는 2번째 인덱스 까지의 숫자를 고려했을 때의 최댓값이 저장될 것이다.

 

이 때, 만약 이전 인덱스 까지의 연속합이 음수라서 이전까지의 합에 현재 수를 더하는 것 보다

현재 수 만을 갖고있는게 더 큰 경우에는

이전까지 연속합을 끊어내고 현재 인덱스부터 새로운 구간합을 만들어가야 한다.

 

이러한 부분들을 고려하여 작성한 파이썬 코드는 다음과 같다.

n = int(input())
nums = list(map(int, input().split()))

INF = -int(1e9)
dp = [INF]*n

if n<2:
  dp[0] = nums[0]

else:
  dp[0] = nums[0]
  dp[1] = max(nums[1], dp[0]+nums[1])
  for i in range(2, n):
    dp[i] = max(dp[i-1]+nums[i], nums[i])

print(max(dp))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !