[알고리즘/동적 계획법] 1912 번 : 연속합 - python

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

1912번: 연속합

 

---

• 문제
• 소요시간: 17분 5초

---

• 설계하기(접근방법) 

1. n을 입력받는다

 

2. 알고리즘 해석

1) 중간에 음수가 나와도, 연속된 수의 합이 0 이하로 떨어지지 않는 이상, 계속 더해나가는 것이 이득이다

ex) 1,2,3,-2,3,5

-> 1 3 6 4 7 12

 

2) 하지만 0이하로 떨어지는 경우 그 자리에서 덧셈을 멈춰야 한다

i: ex) 1 2 3 -8 1 2

-> 1 3 6 -2 -1 1

i이 경우가 아닌

ii : ex) 1 2 3 -8 1 2

-> 1 3 6 -2 1 3

ii가 되어야 한다

 

즉 이전 항을 검사하여, 이전 항이 음수라면, 현재 자신의 원소만 더한다

아니라면 이전항 + 자신의 원소를 더한다

 

동적 계획법으로 풀면

arr = [입력받는 숫자]

dp= []

 

dp[i-1] < 0 , 이전항이 0보다 작다면

dp[i] = arr[i] 현재 dp는 현재 원소값이고

 

dp[i-1] >=0, 이전항이 0보다 크면

dp[i] = dp[i -1] + arr[i]

이전 dp값에 현재 원소값을 더해 최대값을 늘려나간다

 

3. max(dp)를 출력한다

 

 

 

---

• 코드(출력)

n = int(input())

dp = [0 for i in range(n)]


arr = list(map(int, input().split()))


for i in range(n):
    if i == 0:
        dp[i] = arr[i]
    else:
        if dp[i-1] < 0:
            dp[i] = arr[i]
        else:
            dp[i] = dp[i-1] + arr[i]

print(max(dp))

 

---

• 얻어갈 부분

1. 순차적으로 해결해나가려면 어떤 알고리즘이 필요할지 생각해서 풀 수 있었다.

2. 처음에 음수를 고려 안하고 풀어 답이 반만 맞았다. 다음에는 꼼꼼히 문제를 읽자