문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
풀이
1차 시도
문제는 되게 간단하게 써있다. 문제가 간단한 만큼 요점만 빨리 찾으면 간단히 해결되는 문제다. 그러나 나는 많이 헤맸다.
처음에 생각해낸 방법은 양수만 쭉 더하다가 음수가 나오면 멈추고, 다시 양수가 나오면 양수끼리 더한다음 원래 있던 값이랑 비교해서 큰 값을 집어넣고 그런식으로 했다.
1차 코드
n = int(input())
numbers = list(map(int,input().split()))
dp = [0 for _ in range(n)]
dp[0] = numbers[0]
if numbers[0] > 0:
summ = numbers[0]
for i in range(1,n):
if numbers[i] > 0:
# 양수끼리 더하기
summ += numbers[i]
dp[i] = max(dp[i-1],summ)
elif numbers[i] < 0:
# 음수가 나왔으니 끊긴다.
summ = 0
dp[i] = dp[i-1]
print(dp[n-1])근데 이 논리에는 아주 큰 허점이 있었다.
예를 들면, 1, 2, 3, -4, 5를 입력받았다고 생각해보자. 그러면 1+2+3 = 6 이지만 1+2+3+(-4)+5 - 7 이다. 음수를 포함해서 연산해도 값이 더 커지는 경우가 있다는 것. 아예 논리를 뒤엎어야 했다.
2차 시도
아무리 생각해도 감이 오질 않아서 구글링을 했다. 다이나믹 프로그래밍이라면 점화식이 나와야 할텐데, 왜 내가 점화식을 생각하지 못했는지 블로그를 보면서 깨달았다.
나는 답을 dp 리스트의 마지막 인덱스를 이용해서 출력하려고 했다. 즉, dp리스트에 최댓값만을 계속 넣고싶어했다. 이게 내 편견이자 고정관념, 허점이었다. maxx라는 최댓값을 넣는 변수를 선언해서 그 변수에 최댓값을 넣어주고, dp리스트는 계속 합을 넣어주는 것이 맞았다. 왜냐하면, 연속합은 일정 범위를 더해야 하기 때문에 값들의 합이 필요하다. 그 값이 설령 최댓값이 아니더라도.
그래서 나온 점화식은
dp[n] = dp[n-1] + numbers[n]
근데 이것이 끝이 아니라, 고려해줘야 할 사항이 2가지 정도 있다. 이대로만 코드를 짜면 안된다.
dp[n-1] < 0dp[n-1] + numbers[i] > 0
이 2가지를 고려해야 한다. 예를 들면, -5와 6을 입력 받았을때, -5를 과감히 버려야한다. 그러나 그냥 무턱대고 버려버리면 -1, -2를 입력받았을 때 -2를 선택해버리는 최악의 경우가 생길 수 있으니 값을 비교하고 버리자.
2번째 경우를 생각해 내는 것이 가장 어려웠다고 할 수 있다.저 경우가 바로 첫번째 시도때 나온 반례까지 포함해주는 경우다.
왜냐하면, 예를 들어보자. dp[n-1] + numbers[i] 가 음수라고하면, 그 다음값이 아무리 크다해도 이 값을 버리는게 더 크다. 하지만 음수가 아닐때, numbers[i]가 음수라고 하여도, numbers[i+1] 이 존재할 때 그 값이 numbers[i]보다 절댓값이 큰 양수라고하면 음수 numbers[i]를 안고 가는 것이 연속합이 더 크게 나온다!
정답 코드
n = int(input())
numbers = list(map(int,input().split()))
dp = [0 for _ in range(n)]
dp[0] = numbers[0]
maxx = dp[0]
# dp[n] = n + dp[n-1]
for i in range(1,n):
if dp[i-1] < 0:
dp[i] = max(dp[i-1], numbers[i])
elif dp[i-1] + numbers[i] > 0 :
dp[i] = numbers[i] + dp[i-1]
if maxx < dp[i]:
maxx = dp[i]
print(maxx)