백준 1912번 - 연속합

 

연속된 수의 합의 최댓값을 구하는 문제이다. 입력값의 개수가 100,000까지 가능하기 때문에, 모든 경우를 비교하면 시간 초과가 뜰 것이다. 그러므로 불필요한 경우를 dp를 이용해서 제거해야 한다.

 

예제 입력 1을 보면 10개의 수를 입력받는데, 이 중에서 앞의 4개만 예시로 들자.(10, -4, 3, 1)

비교해야 하는 모든 경우의 수를 보면,

1.  10

2.  10   -4

3.  10   -4   3

4.  10   -4   3   1

5.         -4

6.         -4   3

7.         -4   3   1

8.               3

9.               3   1 

10.                  1

 

총 10개의 경우를 비교해야 하는데, 2번부터 4번까지는 5번부터 7번까지의 경우에 10, 즉 A[0]을 더한 값이고 1번은 A[0]이다. 또한 6번과 7번은 8번과 9번에 -4, 즉 A[1]을 더한 값이다. 그러므로 밑에 쓴 것처럼 A의 마지막 원소부터 탐색하면서, A의 값과 이전 시행의 값에 A를 더한 값을 비교하면 될 것이다. 

 

1.  1

2.  4   3

3.  0   -1   -4

4.  10  9    6   10

 

이렇게 10가지 경우를 모두 비교하면 시간 초과가 뜰 것이다. 그러므로 우리는 1번부터 4번까지 진행하면서 필요없는 비교 대상들을 제거해주면 된다. 1번에서 2번으로 넘어갈 때는 3을, 2번에서 3번으로 넘어갈 때는 -4를 제거해줘야 한다.

즉, 매번 값을 더해줄 때 A의 원소와 dp에 추가한 값에 A를 더한 값중에 큰 값을 dp에 넣어주면,

 

1.  1

2.  4   (3)

3.  0   (-4)

4.  10  (10) 

 

이런 식으로 N번의 시행으로 최댓값을 구할 수 있다.

 

##변수 선언 부분##
A = []
dp = []
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split()]
    dp.append(A[-1]) #A의 마지막 원소부터 차례대로 탐색한다.
    for i in range(N-2, -1, -1):
        dp.append(max((dp[N-i-2]+A[i]), A[i])) #탐색하는 A의 원소와 이전 값에 A의 원소를 더한 값을 비교
    print(max(dp))

 

너무 어렵게 생각하다 보니 시간이 조금 오래 걸렸다.