백준 1912 연속합 파이썬 문제풀이 (python 누적합)

문제 보러가기

 

 

백준 연속합 파이썬 문제풀이

n개의 정수 수열이 주어지면, 

몇 개의 연속 수를 가지고 만들 수 있는 가장 큰 합을 구하는 문제이다.

 

이전 포스팅의 문제와 달리, 몇 개 연속인지 알려주지 않는다.

그렇다면 일일히 찾아야한다는 점.

 

그러면 더더욱 누적합을 잘 이용해야한다.

 

N = int(input())
arr = list(map(int, input().split()))
accum = [0 for _ in range(N+1)]
answer = float('-inf')

# 누적합 구하기
for i in range(N):
    accum[i+1] = accum[i] + arr[i]

cont = []
# 연속되는 수열 합 구하기
for i in range(1,N+1):
    list = []
    for j in range(N+1 - i):
        list.append(accum[j+i] - accum[j])
    cont.append(list)

for lst in cont:
    m = max(lst)
    answer = max(answer, m)
print(answer)

누적합 배열을 구하고, 

누적합끼리 연산하면 연속된 수의 합을 구할 수 있는 규칙을 이용한 코드를 구현했다.

 

n 번째 연속 2개 수열 합을 구하기 위해

누적합의 n+2 값에서 n값을 빼면 구해지는 규칙말이다. 

 

\(contin2[n] = accum[n+2] - accum[n]\)

2를 변수로 해서 적용 가능하다. 

 

하지만 메모리 초과..

 

 

단순히 cont 배열의 크기가 너무 커서하면 재깍재깍 최대를 구해보자.

N = int(input())
arr = list(map(int, input().split()))
accum = [0 for _ in range(N+1)]
answer = float('-inf')

# 누적합 구하기
for i in range(N):
    accum[i+1] = accum[i] + arr[i]

# 연속되는 수열 합 구하기
for i in range(1,N+1):
    list = []
    for j in range(N+1 - i):
        list.append(accum[j+i] - accum[j])
    answer = max(answer, max(list))
print(answer)

 

이번엔 시간초과... 

이중 반복문으로 인해 

연산이 100,000의 제곱이 되는 모양이다.

 

그렇다면 다른 방법으로 풀어야한다.

이때 이전까지의 기록들을 사용하지 않는 시점이있다.

 

보통 누적해서 많이 더하면 최대값이 되는게 일반적이지만,

여태까지 더한 누적보다 더 큰 수가 있다면 거기서부터 다시 누적하는 방법.

 

이러한 방법으로 풀어야한다.

 

# 누적합 구하기
for i in range(N):
    accum[i+1] = max(arr[i] ,accum[i] + arr[i])

누적합을 구할 때 이렇게 더 좋은 값이 있으면 그걸 선택하는 방향

이것이 DP와 관련된 방식이다. 

 

정답 코드

N = int(input())
arr = list(map(int, input().split()))
accum = [float('-inf') for _ in range(N+1)]

# 누적합 구하기
for i in range(N):
    accum[i+1] = max(arr[i] ,accum[i] + arr[i])

print(max(accum))

누적합의 경우도, 모든 수열이 양수란 법은 없으므로

음의 무한대를 기저로 깔고 간다.