[백준 BOJ] 13398 연속합 2 (python)

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

13398번: 연속합 2

 

🔥 시간초과 코드

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

dp1 = [0 for _ in range(n)]
dp1[0] = lst[0]
if n > 1:
    for i in range(1, n):
        dp1[i] = max(lst[i], dp1[i-1] + lst[i])

result1 = max(dp1)

result2 = lst[0]
for i in range(n):
    if lst[i] < 0:
        lst2 = [x for x in lst]
        lst2.pop(i)
        dp = [0 for _ in range(n-1)]
        dp[0] = lst2[0]
        if n > 1:
            for j in range(1, n-1):
                dp[j] = max(lst2[j], dp[j-1] + lst2[j])
        result2 = max(max(dp), result2)

print(max(result1, result2))

 

 

⭕ 접근법

1. 이전에 풀었던 연속합과 같은 유형이라 그 방식 그대로 풀었습니다.
2. 일단 아무것도 제거하지 않은 상태로 연속된 수의 합 중 가장 큰 합을 구했습니다.
   • dp1이 i자리에서 구할 수 있는 가장 큰 연속합을 저장한 리스트입니다.
   • dp1[0]에 처음 나오는 수를 저장하고 그 뒤부터 비교하며 dp1에 저장해나갔습니다.
3. 마찬가지로 주어지는 수열에서 하나를 뺀 수열을 새로 만들고, 2번을 반복했습니다.
   • lst[i] < 0 의 조건을 작성한 이유는 제외할 수가 양수라면 의미가 없는 작업이기 때문입니다.
4. 모든 수를 한 번씩 빼며 가장 큰 연속합을 갱신했습니다.
5. 예제에는 잘 작동했지만 O(N^2) 으로 시간초과...

시간복잡도를 줄이기 위해 result2를 갱신하는 부분을 어떻게 처리해야 할 지 고민했습니다.🤔

 

 

🔥 수정 코드 (통과)

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

result = -1000
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
dp1[0] = lst[0]
dp2[0] = lst[0]
for i in range(1, n):
    dp1[i] = max(lst[i], dp1[i-1] + lst[i])
    dp2[i] = max(dp1[i-1], dp2[i-1] + lst[i])
        
for i in range(n):
    result = max(result, dp1[i], dp2[i])

print(result)

 

⭕ 해설

1. 하나를 제외한 경우를 따로 빼서 구하지 않고 하나의 루프에서 제외하지 않은 경우와 함께 계산했습니다.
2. 결과의 초기값은 어떤 수열이든 최솟값이 될 수 있는 값인 -1000으로 설정했습니다. 
3. dp1, dp2를 나누었습니다.
   • dp1에는 제외한 수가 없을 때의 연속합의 최대값을 채워갑니다.
   • dp2에는 어떤 수를 제외했을 때의 연속합의 최대값을 채워갑니다.
4. i번째 수를 제외하고 생각한 경우와 아닌 경우를 비교하여 큰 값을 저장합니다. 💡
   • i자리를 제외했다면 어떤 수도 제외하지 않고 구한 연속합을 그대로 가져옵니다.
   • i자리를 제외하지 않았다면 어떤 수를 제외했을 수도 있는 연속합에 i자리 수를 더해줍니다.
   • 위의 두 수를 비교하여 큰 값을 저장합니다.