https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 연속적으로 순자를 선택한 후 그 합이 최대가 되도록 하면 해결할 수 있는 dp 문제입니다. 따로 dp 리스트를 만들기보다 입력받은 리스트를 그대로 활용하면 보다 간단하게 해결할 수 있는 문제였습니다. 먼저 예시를 통해 알아봅시다.
0번째 인덱스까지의 최대의 합은 0번째 인덱스 그대로입니다.
| 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
1번째 인덱스까지의 최대의 합은 1번째 인덱스 그대로가 아닌 0번째 + 1번째입니다.
| 10 | 6 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
2번째 인덱스까지의 최대의 합은 2번째 인덱스 그대로가 아닌 0번째 + 1번째 + 2번째입니다.
| 10 | 6 | 9 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
위와 같은 방식으로 6번째 인덱스 까지는 인덱스 그대로가 아닌 합으로 이루어집니다. 이는 아래의 그림과 같습니다.
| 10 | 6 | 9 | 10 | 15 | 21 | -14 | 12 | 21 | -1 |
다만, 7번째 인덱스까지의 최대의 합은 0번째부터 7번째까지의 합이 아닌 7번째 인덱스 그 자체입니다. 따라서 7번째 인덱스는 그대로 유지됩니다.
| 10 | 6 | 9 | 10 | 15 | 21 | -14 | 12 | 21 | -1 |
8번째 인덱스까지의 최대의 합은 8번째 그대로가 아닌 7번째 + 8번째입니다.
| 10 | 6 | 9 | 10 | 15 | 21 | -14 | 12 | 33 | -1 |
9번째 인덱스까지의 최대의 합은 9번째 그대로가 아닌 7번째 + 8번째 + 9번째입니다. 위의 표를 기반으로 점화식을 작성하면 다음과 같습니다.
data[i] = max(data[i], data[i-1] + data[i])
이를 소스코드로 표현하면 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
|
n = int(input())
data = list(map(int, input().split()))
for i in range(1, n):
data[i] = max(data[i], data[i] + data[i-1])
print(max(data))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1904번: 01타일(Python) (0) | 2022.01.28 |
|---|---|
| 백준 알고리즘 2156번: 포도주 시식(Python) (0) | 2022.01.25 |
| 백준 알고리즘 1149번: RGB거리(Python) (0) | 2022.01.24 |
| 백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python) (0) | 2022.01.20 |
| 백준 알고리즘 2579번: 계단 오르기(Python) (0) | 2022.01.19 |