1912 연속합 with 파이썬 (feat. DP, 동적 프로그래밍)

08.18.2023

 

1. 문제

                      시간 제한                             메모리 제한            제출                   정답            맞힌 사람         정답 비율

1 초 (추가 시간 없음)

128 MB

129671

48065

34077

35.739%

 

문제

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

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

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

2. 설명

이 문제의 핵심은 Dynamic Programming, 동적 계획법을 이용하여 이전까지의 모둔 숫자의 합 중 최대값을 기록하는 것입니다.

[10, 1, 3, 5 , -4] 라는 배열이 들어왔다고 예시를 들어봅시다.

우리는 10+1, 10+1+3, 10+1+3+5 의 과정을 거쳐서 정답을 구해낼 것입니다. 

이 과정에서 우리는 이전 숫자의 합이 필요하다는 사실을 알았습니다.

 

마지막 -4는 어떨까요?

단순히 마이너스라 값을 제외해버리기엔 음수가 징검다리 역할을 해 더 큰 수열을 만들 수 있습니다.

예를들어, [10, -5, 3, 2, 1] 배열에서 -5이기 때문에 수열을 잘라버리면 10이 최대 값이 됩니다.

그러나 포함시킨다면 총 합 11의 수열이 나오게 되죠. 음수를 포함시키는 게 더 이득이 됩니다.

 

그렇다면 우리가 해야할 연산은 10+1+3+5가 더 큰지, 10+1+3+5-4가 더 큰지 비교하는 연산입니다.

둘 중 더 큰 값을 저장한다면, 음수에 인터럽트 받지 않고 가장 큰 수열을 도출할 수 있습니다.

 

3. 최종 코드

제가 작성한 최종 코드는 다음과 같습니다.

위에서 설명한 것과 같이 현재 값과, 이전값들의 합과 현재 값을 비교해 더 큰 값을 넣고, 그 중에서 가장 큰 값이 정답이 됩니다.

N = int(input())
arr = list(map(int, input().split(" ")))

for i in range(1,len(arr)):
    arr[i] = max(arr[i], arr[i]+arr[i-1])

print(max(arr))

4. 결론

이 문제 관련해서 글 몇개를 봤는데, 설명이 별로 없고 코드만 나와있어서 코드를 보고 혼자 이해했어야 했습니다.

제 설명이 도움이 되길 바랍니다.

그리고 첨부터 잘 푸는 사람들은 정말 극소수인 것 같습니다.

그러니까 온라인 소스 참고하는 것을 너무 부끄럽게 생각하지 마셨으면 좋겠습니다.