백준: 13398 연속합 2

문제

13398번: 연속합 2

 

문제 풀이

 이전에 풀었던 1912 연속합에서 하나의 숫자를 뺄 수 있는 조건이 추가된 문제이다. 따라서 문제 풀이는 다음과 같이 접근할 수 있다.

 

1. 아무것도 빼지 않는 연속합을 메모 이제이 션 한다.
2. 구해진 연속합에서 중간에 수를 제거한 경우에 대한 값을 메모이제이션 한다.

 1번의 경우는 연속합 문제에서 다루었다. 그럼 2번의 경우는 어떤식으로 찾을 수 있을까? 조금만 생각해보면 쉽게 답을 찾을 수 있다. 예를 들어 4개의 값이 있다면 OOXO와 같이 2번 인덱스의 값을 제외하고 싶다면 1번으로 구해진 메모이제션의 1번 인덱스와 현재 입력된 값 중 3번 인덱스의 값을 더하게 되면 2번 인덱스를 제외한 값을 구할 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(input())
    nums = list(map(int, stdin.readline().split()))

    origin, skip = [0] * n, [0] * n
    origin[0] = skip[0] = nums[0]
    answer = nums[0]

    for i in range(1, n):
        origin[i] = max(origin[i - 1] + nums[i], nums[i])
        skip[i] = max(origin[i - 1], skip[i - 1] + nums[i])
        answer = max(answer, max(origin[i], skip[i]))

    print(answer)

 코드에서 origin은 숫자를 제거하지 않을 때 연속합을 메모이제이션하고, skip은 중간에 하나의 숫자를 제거할 때 메이이제이션한다.