SW
[백준 1912] 연속합 본문
0. 제목
- 백준 1912 연속합
- BOJ 1912 연속합
- C++ 1912 연속합
1. 문제
https://www.acmicpc.net/problem/1912
2. 풀이
- DP 방식을 이용하였다.
- 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이 목적이다.
- 예를 들어, 배열의 값들이 10, 20, -100, -500, 700, 30 이라고 할 때, dp[1] = 10, dp[2] = 30, dp[3] = -70, dp[4] = -500, dp[5] = 700, dp[6] = 730 이다.
- 이 배열 dp 의 원소 값들을 구하는 규칙은 다음과 같다.
- 만약 dp[i]를 구하려고 할 때 dp[i-1] 가 음수라면 dp[i] = arr[i] 로 업데이트 해주고 양수라면 dp[i] = dp[i-1] + arr[i] 를 해주면 된다.
- 그렇게 되면 dp[i] 는 arr[i] 를 포함한 가장 큰 합이 될 것이다.
- 중요한 부분은 바로 다음 부분이다.
- 앞서 구한 배열 dp의 원소값들 중 최댓값을 구해야 한다. 그것이 문제에서 요구하는 것이다.
3. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int n;
int arr[100001];
int dp[100001];//dp[i] 에는 arr[i] 를 포함하였을때의 최대 합을 담는다.
int max;
cin >> n;
for(int i = 1;i <= n; i++){
cin >> arr[i];
}
//max 로도 구현 가능
dp[1] = arr[1];
max = dp[1];
for(int i = 2; i <= n; i++){
if(dp[i-1] + arr[i] > arr[i]) //if(dp[i-1]) > 0)
dp[i] = dp[i-1] + arr[i];
else
dp[i] = arr[i];
}
//이 부분부터가 핵심
max = dp[1];
for(int i = 2; i <= n; i++){
if(max < dp[i])
max = dp[i];
}
//cout << dp[4]; 1, 2, 3, -100 일때 dp[4] = -96 이다. dp가 정답이 아니라 dp들을 비교하여 최대 값이 정답이다.
cout << max << '\n';
return 0;
}
|
'대학교 > Algorithm' 카테고리의 다른 글
[백준 11047] 동전 0 (0) | 2020.02.05 |
---|---|
[백준 10451] 순열 사이클 (0) | 2020.02.02 |
[백준 1707] 이분 그래프 (0) | 2020.02.01 |
[백준 11724] 연결 요소의 개수 (0) | 2020.01.29 |
[백준 2750] 수 정렬하기 (0) | 2020.01.28 |
Comments