득이공간
[백준 C++] 1912 연속합 - 다이나믹프로그래밍 본문
#include <iostream>
#include <vector>
using namespace std;
vector<int> DP;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int N;
cin >> N;
DP.reserve(N);
int Num;
cin >> Num;
DP.emplace_back(Num);
int Max = Num;
for (int i = 1; i < N; ++i)
{
cin >> Num;
Num = max(Num, DP[i - 1] + Num);
DP.emplace_back(Num);
Max = max(Max, Num);
}
cout << Max;
}
1~N 사이의 구간합 중 최대값을 출력하는 DP 유형의 문제입니다.
풀이 과정은 간단합니다.
N개의 수를 입력받을 때 DP 배열에 해당 수 또는 해당 수를 포함한 이전 수들과의 구간합 중에서 큰 수를 저장해줍니다.
DP 배열을 모두 채운 후에는 그 중 가장 큰 값을 출력해주면 됩니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1967 트리의 지름 - 깊이우선탐색 (0) | 2024.03.05 |
---|---|
[백준 C++] 1504 특정한 최단 경로 - 다익스트라 (0) | 2024.03.05 |
[백준 C++] 1043 거짓말 - 분리집합 (0) | 2024.03.04 |
[백준 C++] 17070 파이프 옮기기 1 - 다이나믹프로그래밍 (0) | 2024.03.04 |
[백준 C++] 15649 N과 M (1) - 백트래킹 (0) | 2024.03.04 |