[BOJ][⚪2][백준#01912] 연속합

문제 출처

BAEKJOON Online Judge #1912

문제

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

출력

33

예제 2

입력

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

출력

14

예제 3

입력

5
-1 -2 -3 -4 -5

출력

-1

My Sol

N = int(input())
dp = list(map(int, input().split()))
i = 1
maxV = dp[0]
while i < N:
    dp[i] = max(dp[i-1]+dp[i], dp[i])
    maxV = max(maxV, dp[i])
    i += 1

print(maxV)

dp를 이용하는 문제인 것 같았다. 그런데 중간에 중단하는 점을 어떻게 알아야하지 생각해보다가 maxV 변수를 두어 매번 최댓값을 확인해 갱신해주었다.

결과

맞았습니다!!

모범답안

출처

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

    for i in range(1, n):
        if sequences[i-1] > 0:
            sequences[i] += sequences[i-1]
    print(max(sequences))

연산 시간이 절반정도로 꽤 빠른 풀이가 있어서 분석해보려 한다. 이전 값이 0보다 큰 경우 이후 값과 더하고, 아니라면 넘어간다. 그렇게 되면 매 자리마다 가질 수 있는 최대의 크기의 값을 가지므로 전체를 max 취하면 최댓값을 구할 수 있다.

나 역시 매번 maxV로 하지 않고 dp 배열 전체에 대해 max를 취하면 되는 것이었지만 그 외에는 다른 로직이 없는데 왜 이렇게 속도가 차이가 나는지 모르겠다.

모범답안 2

출처

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

for i in range(1,n):
    num[i]=max(num[i], num[i-1]+num[i])
print(max(num))

나와 비슷하지만 조금 더 빠른 풀이였다. 차이점은 dp 배열을 나중에 한 번에 max를 취하느냐 매번 max를 취해 갱신하느냐 차이였는데, 이 차이가 꽤나 큰 연산 시간의 차이를 가져오는구나 싶었다.