백준 알고리즘 | 1912 : 연속합 (Python / 파이썬)

---

연속합 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	128 MB	72646	21512	14818	28.977%

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

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보다 작거나 같은 정수이다.

​

출력

첫째 줄에 답을 출력한다.

​

알고리즘 분류

다이나믹 프로그래밍

---

 

백준 알고리즘 # 1912번 : 연속합

출처:  https://wikidocs.net/3142

n = int(input())
a = list(map(int, input().split()))

for i in range(1, n):
    a[i] = max(a[i], a[i - 1] + a[i])
    
print(max(a))

풀이

공부한 내용을 까먹지 않게 최대한 하루에 한 문제씩 풀려고해요!

​

아직 잘 하지 못하는 다이나믹 프로그래밍(DP) 문제이지만 쉽게 생각해봤어요.

먼저 n 변수로 정수의 개수를 입력받고, list로 다음 예시들을 쭉 입력 받았어요.

​

다음으로 for 반복문으로 1부터 정수의 개수만큼 돌려서 a[1~9]까지 list에 새로 초기화시켰어요.

​

key point

초기화시킬 때 max함수의 특징을 이용하면 되는데요.

하나의 예시를 들어서

a = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

​

위 list에서 i = 8로 max(a[8], a[7] + a[8])을 비교하게 되면

max(21, 33)로서 max인 수 33이 a[8]에 저장되요.

​

이렇게 i = 1부터 9까지 쭉 a[1~9]를 초기화시키고

마지막에 print(max(a))를 출력하면 그 안에서 max인 값이 출력되면서 풀이 끝!👏

​

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏

wook2124/Algorithm-Test

최종 소스코드