[BOJ/백준] 13398 연속합 2

● [문제번호 13398] 연속합 2

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: 1912 연속합 문제를 참고해서 풀려다가 뭔가 꼬이는 바람에 구글링을 했는데

간단하게 풀 수 있던 문제였다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[0][index] : index까지 수열의 연속합 (수열에서 0개 제거)
dp[1][index] : index까지 수열의 연속합 (수열에서 1개 제거)

 

2. 점화식 찾기

→ 0개 제거된 경우는 1912 연속합 문제 처럼 동일하게 한다.

1개 제거된 경우는 직전의 index에서 {0개 제거된 배열에서 가져온 것}과, {1개 제거된 배열에서 가져온 것 + 현재 index값을 더한 것} 중 큰 것을 저장하면 된다.

 

즉, 아래 그림에서 {1번}과 {2개의 2번의 합} 중 큰 것을 고르면 된다.

그렇게 선택된 25의 의미는 {10, -4, 3, 1, 5, 6} 중 1개를 제거해서 가장 큰 연속합이라는 뜻이다.

 

dp[0][index] = max(dp[0][index - 1], 0) + num[index];
dp[1][index] = max(dp[0][index - 1], dp[1][index - 1] + num[index]);

 

3. 초기값 정하기

→ 시작 값만 저장하면 되므로

dp[0][1] = num[1]

dp[1][1] = num[1]

 

예제 입력1 풀이과정

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: 풀이과정 참고

https://ladun.tistory.com/50

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 수열
// dp[0][index] : index까지 수열의 연속합 (수열에서 0개 제거)
// dp[1][index] : index까지 수열의 연속합 (수열에서 1개 제거)
int num[100001];
int dp[2][100001];
int N;

void program()
{
    // 초기값
    dp[0][1] = num[1];
    dp[1][1] = num[1];
    
    // 점화식
    for(int index = 2; index <= N; index++)
    {
        dp[0][index] = max(dp[0][index - 1], 0) + num[index];
        dp[1][index] = max(dp[0][index - 1], dp[1][index - 1] + num[index]);
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    for(int n = 1; n <= N; n++)
        cin >> num[n];
    
    program();
    
    for(int i = 0; i <= 1; i++)
    {
        for(int j = 1; j <= N; j++)
            cout << dp[i][j] << " ";
        cout << "\n";
    }
    
    
    int sol = max(dp[0][1], dp[1][1]);
    
    for(int i = 0; i <= 1; i++)
        for(int j = 1; j <= N; j++)
            sol = max(sol, dp[i][j]);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225