[BOJ 13398 // C++] 연속합 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13398번 문제인 연속합 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/13398

13398번: 연속합 2

연속한 수(단, 중간에 한번 딱 한칸 건너뛸 수 있다)들의 합 가운데 최댓값이 무엇인지 구하는 문제이다.

글쓴이는 Dynamic Programming으로 다음과 같이 풀어보았다.

 

N이 4 이상이라고 가정하자.

N-1개의 수까지 보았을 때 다음을 알고 있다고 생각하자.

 

1) (한번도 건너뛰지 않으면서 N-1번째 수를 포함하는 구간합) 중 구간합이 최대인 경우의 구간합 jump0

2) (한번 건너뛴 상태로 N-1번째 수를 포함하는 구간합) 중 구간합이 최대인 경우의 구간합 jump1

3) (한번도 건너뛰지 않으면서 N-2번째 수를 포함하는 구간합) 중 구간합이 최대인 경우의 구간합 oldjump0

4) 출력할 답을 저장한 ans

 

이 때, N번째 수 current를 추가하면, 각 변수는 다음과 같이 계산할 수 있다.

jump0 = max(jump0+current, current)
jump1 = max(jump1, oldjump0) + current

oldjump0 = jump0;

ans = max(ans, max(jump0, jump1))

 

N이 4 이상인 이유는 jump1이 N이 3 이하일 경우 제대로 정의가 안 되기 때문이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
using std::max;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    if (N == 1) { // 예외 N = 1
        int x;
        cin >> x;
        cout << x;
    }
    else if (N == 2) { // 예외 N = 2
        int x, y;
        cin >> x >> y;
        cout << max(max(x, y), x + y);
    }
    else { // Base case N = 3
        int x, y, z;
        cin >> x >> y >> z;
        int oldjump0, jump0, jump1;
        oldjump0 = max(y, x + y);
        jump0 = max(max(z, y + z), x + y + z);
        jump1 = x + z;
        int ans = max(max(jump0, jump1), max(max(x, y), x + y));
        for (int i = 3; i < N;i++) { // N = 4 이상은 Dynamic Programming으로
            int current;
            cin >> current;
            int oldjump0temp = jump0;
            int jump0temp = max(jump0+current, current);
            int jump1temp = max(jump1, oldjump0) + current;
            oldjump0 = jump0;
            jump0 = jump0temp;
            jump1 = jump1temp;
            ans = max(ans, max(jump0, jump1));
        }
        cout << ans;
    }

    return 0;
}