[백준 1912번] 연속합 파이썬 풀이

연속합 

1 초 (추가 시간 없음)

128 MB

137827

51945

36917

36.309%

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1

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

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1

"연속된 수" 의 최대 합을 구하는 문제이다.

 

이 문제를 풀기 위해선 "연속된 수"라는 조건에 주목해야 한다. 나는 처음 연속된 수라는 의미를 '11053번 : 가장 긴 부분 순열' 문제를 풀고 난 직후에 풀어서 그런지 오름 차순 혹은 내림 차순과 같이 일정한 규칙을 가진 수를 의미하는것으로 오해했었으나, 말 그대로 배열에서 서로 붙어 있는 수들을 말 하는 것이었다.

 

n개의 수를 입력받을 것이므로, 메모이제이션 기법을 이용하기 위해 n 만큼의 크기를 가진 dp테이블을 생성하고, dp 테이블의 값에 해당 인덱스까지 이르렀을때의 최대 누적 합을 저장하도록 하였다.

 

문제를 풀기 위한 핵심 아이디어는 다음과 같다.

이전의 수와 현재 수를 더한 값이 0보다 크다면(조금이라도 최대합이란 조건에 이득이 된다면), 현재 수와 현재 수에 이전 수를 더한 값 중 더 큰 값을 dp테이블에 누적 시킨다.(음수를 더해도 0보다 크지만, 최대합이란 조건에는 멀어지므로 이 경우에는 현재 수를 dp테이블의 값으로 누적시켜야 한다.) 만약 이전의 수와 현재 수를 더한 값이 더 작아진다면 => 현재 수를 dp테이블의 값으로 저장한다.

이후 dp테이블의 값 중 가장 큰 값을 정답으로 제출한다.

 

예를 들어 다음과 같은 배열을 상상해보자.

2

-1 3

단순히 0보다 크다는 조건을 적용시켜 dp테이블을 작성하면

dp[0] = -1

dp[1] = -1 + 3 > 0 => dp[1] = 2

과 같은 답이 되어 실제 답은 3이지만 2가 제출되어 오답 판정을 받게된다.

따라서 0보다 클때(조금이라도 더 이득이 될 때), 해당 수를 더한 값이 더 커지는것인지 확인하여 누적해야 한다.

 

위 아이디어를 적용한 코드는 다음과 같다.

n = int(input())


# 최대 합을 저장할 dp테이블
dp = [0]*n

# 임의의 수열 입력받기
data = list(map(int, input().split()))

# "연속된 수"의 의미는 붙어있는 수라는 의미

# 조금이라도 더 큰 수를 들고 가면 이득이므로
# dp[i-1] + data[i] > 0을 만족한다면 조금이라도 큰 값을 들고 다음 수로 넘어갈 수 있으므로 누적한다.
# 단 이때 음수를 더함으로서 값이 더 작아지는 경우를 방지하기 위해 더한값과 더하지 않은 값 둘 중 최대값을 dp에 기록한다.
# 그렇지 않은 경우 dp[i]의 값은 해당 인덱스의 값으로 한다.

dp[0] = data[0]  # 0번째 값은 그대로 들고 가야 하므로

for i in range(1, n):
    if dp[i-1] + data[i] > 0:
        # 점화식을 만족한다면
        # 음수를 더함으로서 수가 더 작아질 수 있으므로 더한것이 더 큰지, 안 더한것이 더 큰것인지를 확인한다.
        dp[i] = max(data[i], dp[i-1] + data[i])
        # dp[i] = dp[i-1] + data[i]  # 누적시킨다(조금이라도 수를 다음 수에 더하기 위하여)
    else:  # 만족하지 않는다면 값을 저장한다.
        dp[i] = data[i]

# dp 테이블에 저장된 값 중 최대 값이 정답이 된다. (누적 합이므로)
print(max(dp))

 

다이나믹 프로그래밍 문제가 늘 그렇듯, 원리를 파악하는것이 어렵지 정확한 조건을 파악하고 점화식을 만들면 비교적 쉽게 문제가 풀리는 것 같다.

하지만 문제를 풀기 위해 충분한 시간을 쏟지 않고 단순히 코드만 이해하려한다면 새로운 문제를 대면했을 때, 문제를 쉽게 해결할 수 없는 것 같다. 더 많은 문제를 풀어봐야겠다.

 

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

1912번: 연속합