백준 1912 [python]

백준 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차 시도 코드

import sys

N = int(sys.stdin.readline().rstrip())

arr = list(map(int, sys.stdin.readline().split()))

dp = [[-1001] * (N+1) for i in range(N+1)]

maxV = -1001
def func(start, length) :
    global maxV
    if length == 1 :
        if maxV < arr[start] :
            maxV = arr[start] 
        return arr[start] 

    if dp[start][length] != -1001 :
        return dp[start][length]

    pl = start 
    pr = start + length - 1
    p = (pl + pr) // 2

    left = func(pl, (length +1) // 2)
    right = func(p+1, (length // 2))

    if maxV < left + right :
        maxV = left + right 

    dp[start][length] = left + right    
    return dp[start][length]

for length in range(1, N+1) :
    for start in range(N - length + 1) :
        func(start, length)

print(maxV)

1차 시도 풀이

1. dp 배열을 2차원으로 선언하고 연속되는 수의 합을 전수조사 한다. 

2. 길이가 1인 합부터 N인 합의 결과를 도출하기 위해 재귀 호출을 통해 이를 처리한다. 
   길이 N인 경우 반으로 쪼개가며 dpTable에 합의 결과 있는지 확인 
   Ex) N이 10인 경우 0 ~ 4와 5 ~ 9의 합의 결과가 dpTable에 있는지 확인 없으면 재귀를 통해 값을 계산한다. 

3. dpTable에 없다면 재귀 호출을 통해 값을 계산하고 dpTable에 저장한다. 

4. 재귀를 끝내며 연속된 수의 합을 구한다. 

결과

당연한 결과이지만 메모리 초과 발생
N이 100,000일 때 100,000 * 100,000 배열을 생성해야 하므로 엄청나게 큰 메모리를 사용한다.
이는 통과할 가능성이 없으므로 다른 방법을 찾기로 함 

2차 시도 코드

import sys

N = int(sys.stdin.readline().rstrip())

arr = list(map(int, sys.stdin.readline().split()))

dp = [0] * (N + 1)

maxVal = -1001
for i in range(1, N+1) :
    dp[i] = max(dp[i-1] + arr[i-1], arr[i-1])
    maxVal = max(dp[i], maxVal)

print(maxVal)

2차 시도 풀이

1. dp 테이블에 현재 idx 위치 까지의 연속된 수 중 최대값을 저장한다.
   n까지의 연속된 수의 최대값과 n의 값 중 최대값이 누구인지 구하고 dp[idx]에 저장 
   dp[i] = max(dp[i-1] + arr[i-1], arr[i-1])

2. 해당 인덱스의 최대값과 현재 전체 연속된 수의 최대값과 비교하여 연속된 수의 최대값을 결정한다. 
   maxVal = max(dp[i], maxVal)

3. 결과를 출력한다.

결과

마무리

1차 시도가 실패할 것을 알고 있었으나 그래도 이왕 접근한 방식대로 어떻게든 구현해보고 싶어 구현해봤다. (후회는 없다.)
DP 문제를 풀 때 너무 재귀적으로만 접근하려는 것 같다. 상황에 따라 어떤 방법을 적용해야할지 알 수 있도록 노력해야겠다.