1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
코드
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
if dp[i-1] <= 0: # 앞의 연속된 수를 더해봤자 최대값을 만드는데에 손해 or 영향 X
dp[i] = arr[i]
else: # 앞의 수를 더하는게 이득
dp[i] = dp[i-1] + arr[i]
print(max(dp))
`dp`배열에 연속된 수들의 합의 최댓값을 저장할 것이다.
반복문을 돌며 `dp` 배열의 값을 구하면 되는데
- 반복문 안에서 `i-1`번째 인덱스의 값을 사용할 것이기 때문에 반복문의 범위는 1 ~ n까지로 한다. 그러기 위해 `dp[0]`의 값은 미리 `arr[0]`의 값으로 초기화해놓는다.
- `dp[i-1]`의 값이 0보다 작거나 같다면 앞의 연속된 수를 다해봤자 수의 합에 손해가 나거나 아무런 영향을 미치지 않는다. 따라서 이 경우에는 $dp[i]=arr[i]$이다. 즉, 본인부터 다시 시작하여 연속합을 구한다.
- `dp[i-1]`의 값이 0보다 크다면 앞의 값들을 포합하면 이득이라는 말이다. 그러므로 $dp[i] = dp[i-1]+arr[i]$이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 22857번 가장 긴 짝수 연속한 부분 수열 (small) (0) | 2023.02.13 |
---|---|
[Python/파이썬] 백준 11055번 가장 큰 증가 부분 수열 (0) | 2023.02.12 |
[Python/파이썬] 백준 11053번 가장 긴 증가하는 부분 수열 (0) | 2023.02.11 |
[Python/파이썬] 백준 2407번 조합 (0) | 2023.02.11 |
[Python/파이썬] 백준 11727번 2Xn 타일링 2 (0) | 2023.02.11 |