알고리즘/알고리즘 문제 풀이
(Python) 백준 1912번 - 연속합
용꿀
2024. 3. 22. 00:59
문제 링크: https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
풀이
Dynamic Programming 문제답게 코드 구현보다는 문제 해결을 위한 아이디어를 생각하는 것이 더 어려운 문제이다.
문제 해결을 위한 아이디어는 다음과 같다.
- 우선 해당 인덱스까지의 최대값을 담을 배열을 선언한다.
- 그 후 처음부터 순회하며 해당 인덱스까지의 최대값을 계산하고 이를 저장한다.
- 해당 인덱스까지의 최대값은 이전 인덱스에서의 최대값 또는 현재 인덱스의 값이 된다.
- 최종적으로 최대값들을 담은 배열에서의 최대값이 정답이 된다.
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split(" ")))
_max = [0] * n
_max[0] = arr[0] # 첫번째 인덱스에서의 최대값은 당연히 첫번째 인덱스가 나타내는 값
for i in range(1, n): # 입력값들을 순회하며
_max[i] = max(arr[i], _max[i-1] + arr[i]) # 현재 인덱스까지의 최대값(현재값 또는 이전까지의 최댓값 + 현재값)을 저장한다.
print(max(_max)) # 모든 인덱스에서의 최댓값 중 최댓값을 출력한다.