백준 1912 연속합 / C++

문제 : 1912

풀이 point

dp를 통해 푸는 문제이다. 가장 최선의 선택을 해보도록 하자.

우리는 특정 구간을 선택해서 쭈욱 더하고 그 값이 최대가 되기를 원한다.(건너뛰기가 안된다.)

그렇다면 어떤 배열에 가장 최선의 선택을 한 최대의 값을 저장해놓으면 어떨까?

풀이 방법

최선의 선택은 무엇일까
예졔 입력 1의 경우
10 -4 3 1 5 6 -35 12 21 -1 이다.
10의 경우에는 양수니깐 얻으면 좋다. -4의 경우에는 좋지 않다. 그러나 -4를 감수하고 뒤로 가면 더 많은 값을 얻을 수 있다.

하지만 우리가 할 것은 가장 최선의 선택을 한 최대의 값을 저장해놓는 것뿐이다. 즉 그래서 2까지 왔을 때 최선의 값은 6이다.

3의 경우에는 어떨까 우리는 3과 그전에 저장해둔 2인덱스까지 왔을 때의 값 6이 있다. 그래서 최대값은 9이다.

1 5 6까지는 쭉 덧셈을 하면 된다. 총 6인덱스까지 왔을 때는 21이다.

-35를 만났을 때 최대는 -14이다.

12를 만났을 때 최대는 -2가 아니다. 12부터 다시 시작하는 12가 최대이다. 그렇게 쭈욱 진행하다보면

가장 큰 값은 32인 것을 알 수 있다.

예제2도 똑같은 방법으로 진행해보면 일반화 할 수 있는 점화식이 나온다.

std::max(dp[i], dp[i]+dp[i-1])

참고로 난 dp배열에 값을 저장해두고 바로 최대값을 저장해두는 배열로 사용했다. (재활용)

그리고 최대값을 출력하기 위해 정렬을 했다만 for문을 진행하면서 매번 비교하여 최대값을 갱신 할 수도 있다.

코드

//백준 1912, 연속합

#include <iostream>
#include <algorithm>
int dp[100'001];

int main (){

    int N;
    std::cin >> N;
    for(int i{0}; i<N; ++i) std::cin >> dp[i];

    for(int i{1}; i<N; ++i){
        dp[i] = std::max(dp[i], dp[i]+dp[i-1]);
    }

    std::sort(dp, dp+N);
    std::cout << dp[N-1];

    return 0;
}

2025-02-03T12:45:59.095Z