[BOJ] 백준 1912번 Python

백준 1912번 Python

https://www.acmicpc.net/problem/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보다 작거나 같은 정수이다.

 

 

출력

---

첫째 줄에 답을 출력한다.

 

반응형

풀이

---

import sys
input = sys.stdin.readline


n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))

dp = [0] * n
dp[0] = nums[0]
ans = nums[0]

for i in range(1, n):
    dp[i] = max(nums[i], dp[i-1] + nums[i])
    if dp[i] > ans:
        ans = dp[i]

print(ans)

 

728x90

조건과 관계없이 해당 문제를 푸는 것은 그리 어렵지 않다.

 

브루트포스 기법으로 모든 임의의 수열에 대해 값을 비교해도 된다.

 

다만, 해당 방법으로 문제를 풀면 문제의 조건에 만족하지 못한다.

 

처음 문제를 접했을 때 여러 방법을 떠올렸다.

 

연속합이라는 제목을 보고 누적합을 고민했다.

 

하지만 일반적인 누적합은 문제에 적용하기 어려움이 있었고, 조건을 추가하여 문제를 풀었다.

 

결국 DP를 이용하여 문제를 풀었다.

 

입력받은 배열과 같은 크기의 DP배열을 새로 만들고 

dp[i] = max(nums[i], dp[i-1] + nums[i])

 

해당 점화식을 사용하였다.

 

자, DP에서 점화식을 구하면 나머지는 구현의 영역이다.

 

초기값 세팅과 나머지 과정을 구현하여 문제를 해결했다.