[BOJ] 1912. 연속합(python)

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

1912번: 연속합

 

1. 문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

2. 입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

3. 출력

첫째 줄에 답을 출력한다.

 

4. 문제 해결

      

      

      

    
    

      <python />
    
import sys

input = sys.stdin.readline

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))

5. 문제 풀이 설명

해당 문제는 DP(Dynamic Programming) 문제이다.

DP문제 풀이법 중 Memorization(기억법) 을 활용해 문제를 풀었다.

num 리스트에 문제에서 입력하는 수열을 저장하고, for문을 통해 Memoriaztion을 사용하였다.

index를 -1로 접근하기 위해서 시작은 1로, 마무리는 n으로 하고 for문을 돌렸다.

      

      

      

    
    

      <python />
    
num[i] = max(num[i], num[i-1] + num[i])

for문에 있는 위의 구절의 의미는 다음과 같다.

num[i] 를 num[i] 또는 num[i-1] 과 num[i] 를 더한 값 중의 max값으로 num[i]를 초기화한다.

이 뜻은 기존에 num[i]가 더 크다면 어차피 값을 더하지 않으므로 초기화를 하겠다는 뜻이고, 만약 num[i-1] + num[i] 가 크다면 값을 더한 것으로 간주, num[i]를 더 큰 값으로 기억해 초기화 하겠다는 뜻이다.

따라서 결국 num[i]의 값은 항상 해당 인덱스가 가질 수 있는 최댓값을 가지고 있으며, i가 증가하면서 n까지 돌게 된다면 각 인덱스에는 모든 경우에서 최댓값을 가지는 수로 저장이 되어 있다.

따라서 max(num)값을 출력해 준다면 최댓값을 구할 수 있다.

 

다시 마음을 잡고 공부를 열심히 해야지!

내 인생 화이팅..!!!!!