반응형
https://www.acmicpc.net/problem/13398
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
[ 문제풀이 ]
1. 수열을 입력받고, arr 배열에 저장합니다.
2. 다음과 같은 점화식을 이용하여 dp 배열을 채웁니다.
dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ] + arr[ i ], arr[ i ] )
do[ i ][ 1 ] = max( dp[ i - 1 ][ 0 ], dp[ i - 1 ][ i ]+arr[ i ] )
3. 이 때, dp[ i ][ 1 ]은 해당 수를 지웠을 때의 최댓값입니다.
4. 모든 dp 배열의 값 중 가장 큰 값을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> using namespace std; int n; int arr[100000]; int dp[100000][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } dp[0][0] = arr[0]; int ans = arr[0]; for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]); dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0]); ans = max(max(ans, dp[i][0]), dp[i][1]); } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 17609번 - 회문 (C++) (0) | 2023.09.19 |
|---|---|
| [ 백준 ] 5569번 - 출근 경로 (C++) (0) | 2023.09.18 |
| [ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++) (0) | 2023.09.16 |
| [ 백준 ] 5549번 - 행성 탐사 (C++) (0) | 2023.09.15 |
| [ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++) (0) | 2023.09.14 |