https://www.acmicpc.net/problem/1912
1차원 DP를 사용하였다. 변수를 최댓값과 진행상황 두가지로 만들어 풀었다. 진행상황과 그 다음 숫자가 더했을 때 0보다 작으면 진행상황을 0으로 갱신하는 규칙과 진행상황을 0으로 하는 과정에서 현재 최댓값이 음수이면 그 다음 숫자와 크기 비교를 하여 더 큰 값을 최댓값으로 갱신해준다. 진행 상황을 더한 경우 0이상이면 현재 진행상황을 갱신하고 최댓값도 진행상황과 현재 최댓값을 비교하여 더 큰 값으로 갱신한다.
ex1.) 1 2 4 -5 3 4 5
순서 | 최댓값 | 진행상황 |
1 | 1 | 1 |
2 | 1 + 2 | 1 + 2 |
3 | 1 + 2 + 4 | 1 + 2 + 4 |
4 | 1 + 2 + 4 | 1 + 2 + 4 - 5 |
5 | 1 + 2 + 4 | 1 + 2 + 4 - 5 + 3 |
6 | 1 + 2 + 4 - 5 + 3 + 4 | 1 + 2 + 4 - 5 + 3 + 4 |
7 | 1 + 2 + 4 - 5 + 3 + 4 + 5 | 1 + 2 + 4 - 5 + 3 + 4 + 5 |
ex2.) -2 -1 -3 -4 -5
순서 | 최댓값 | 진행상황 |
1 | -2 | -2 |
2 | -1 | 0 |
3 | -1 | 0 |
4 | -1 | 0 |
5 | -1 | 0 |
ex3.) 1 2 3 -7 3 4 5 -1
순서 | 최댓값 | 진행상황 |
1 | 1 | 1 |
2 | 1 + 2 | 1 + 2 |
3 | 1 + 2 + 3 | 1 + 2 + 3 |
4 | 1 + 2 + 3 | 0 |
5 | 1 + 2 + 3 | 3 |
6 | 3 + 4 | 3 + 4 |
7 | 3 + 4 + 5 | 3 + 4 + 5 |
8 | 3 + 4 +5 | 3 + 4 + 5 - 1 |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, num; //n은 숫자의 수, num은 원소
int ans = 0, going = 0; //최댓값과 진행상황
vector<int> v; //숫자 배열
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
v.push_back(num);
}
//현재 최댓값과 진행상황을 첫번째 숫자로 갱신
ans = v[0];
going = v[0];
for (int i = 1; i < v.size(); i++) {
if (going + v[i] < 0) { //현재까지 진행한 상황에서 현재 숫자를 더했을 때 음수인 경우
going = 0;
if (ans < 0) { //현재까지 구한 값 중에서 최댓값이 음수인 경우
ans = max(ans, v[i]); //최댓값과 현재 값 중 큰 값으로 대체
}
}
else { //현재까지 진행한 상황에서 현재 숫자를 더했을 때 0이상인 경우
going = going + v[i]; //진행 상황을 현재 숫자와 더해 갱신하고
ans = max(ans, going); //최댓값을 이전 최댓값과 현재 최댓값으로 갱신
}
}
cout << ans;
}
'백준' 카테고리의 다른 글
백준2294 - 동전2 (0) | 2020.02.01 |
---|---|
백준5549 - 행성 탐사 (0) | 2020.01.31 |
백준10844 - 쉬운 계단 수 (0) | 2020.01.30 |
백준2565 - 전깃줄 (0) | 2020.01.28 |
백준11568 - 민균이의 계락 (0) | 2020.01.26 |