1912번: 연속합
https://www.acmicpc.net/problem/1912
문제 정의
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
접근 방법
다이나믹 프로그래밍 문제임을 알고 있어서 DP 테이블을 어떻게 정의해야 할까 고민했다.
예제를 보면서 규칙을 찾으려고 했다. 연속합이므로 연속적인 숫자의 합이니까 이전의 값을 활용해야지 라는 생각으로 접근했는데, 생각보다 정의하기 어려웠다.
다이나믹 프로그래밍이 맞지만, 이 문제는 Memorization을 잘 활용해야 하는 문제였다.
(Memorization(기억법)으로 대표적인 DP 스킬 중에 하나)
문제 풀이의 핵심은 "이전까지 모든 숫자의 합 중 최대값"을 그때그때 기록하는 것이었다.
예를 들어, 10번째 인덱스를 계산할 차례인데, 9번째 인덱스까지의 모든 경우의 수를 다시 계산할 필요는 없기 때문이다.
따라서 이렇게 구할 수 있다.
numbers[i] = max(numbers[i], numbers[i-1] + numbers[i])
문제 해설
식에 맞게 구현하면 된다.
풀이
# 연속합 중 최대가 되는 것 구하기
n = int(input())
numbers = list(map(int, input().split())) # 정수로 이루어진 수열
for i in range(1, n):
numbers[i] = max(numbers[i], numbers[i-1] + numbers[i])
print(max(numbers))
정리
- DP 쉬운 듯하면서 많이 어렵다.
- ㅜㅜ
Uploaded by N2T
