https://www.acmicpc.net/problem/1912
문제
> n개의 정수로 이루어진 임의의 수열이 주어진다.
> 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.
> 단, 수는 한 개 이상 선택해야 한다.
> 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자.
> 여기서 정답은 12+21인 33이 정답이 된다.접근
입력받은 수열에 대해서 현재 수열까지의 합이 큰지, 현재 수 부터 시작하는게 더 큰지를 따져서 둘 중 큰 값을 dp값으로 갖는다.
이 방식으로 각각에 대해 dp값이 나오면 모든 dp값중 가장 큰 값을 찾는다. 이는 특정 수까지의 연속합 중 가장 크게 나온 연속합이라는 뜻이다.
예를 들어 2 1 -4 3 4 -4 6 5 -5 1 이거면
dp1은 2고, dp2는 1과, dp1+1(2+1)중 큰걸 저장한다. 즉 dp2는 3이다.
dp3은 -4, dp2+(-4)하면 -1이 나오고 dp4는 3, -1+3 이므로 3이다.
쭉 가면 dp5 = 7, dp6 = 3, dp7 = 9, dp8 = 14, dp9 = 9, dp10 = 10이다.
이런식으로 그냥 이번부터 새로 연속수를 찾을지 직전번의 최대 수열에 이번까지 연결이 더크면 이걸 가져갈지 고르는거다.
이제 모든 dp가 나오면 이 중 최대를 고른다. 이는 dp8인 14다. 이는 dp4에서 처음 시작된 4,5,6,7,8까지의 연속된 수의 합을 나타낸다.
문제해결
> 수열의 크기와 수열을 입력받는다.
> dp를 구하기 위해 규칙을 수식화 해준다.
수열의 현번째와 전번째 dp값+현번째 값중 더 큰값을 저장한다.
> 입력받은 수열의 크기에 대해 모든 dp값이 구해지면 이중 최대값을 찾아 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> num(n+1);
for (int i = 1; i <= n; i++) cin >> num[i];
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) dp[i] = max(num[i], dp[i - 1] + num[i]);
int Max = dp[1];
for (int i = 2; i <= n; i++) Max = max(Max, dp[i]);
cout << Max << '\n';
}
후기
처음에 누적합으로해서 모든 경우를 다 따져 전부 구해 그 중 젤 큰값을 가져가는식으로 했는데 당연하게도 시간초과가 났다.
그래서 생각한게 어차피 연속합이므로 수가 연속되지 않으면 안되는걸 이용해서 각 단계마다 지금 까지 쌓인거에 이번꺼 더하는거, 이번꺼부터 시작하기 중 큰걸 고르는거로 했다. 언제나 dp는 규칙에 대해 반례를 생각하는게 젤 어렵다.
