백준, BOJ, 1912번 C++ [CPP]

다이나믹 프로그래밍의 문제는 뭔가 자꾸 많이 시킨다.

그래서 이게 DP 문제구나라는 것은 감이 오지만

어떻게 적용해야할 지 감은 바로 안온다..

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

 

---

#맞는 풀이

#include<iostream>
#include<algorithm>

using namespace std;



int N;
int num[100001];
int dp[100001];



int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> num[i];
    }

    int M = -1001;


    for (int i = 1; i <= N; i++) {
        //지금까지의 이번 숫자를 더한 합이 이번에 더할 숫자보다 작다면
        //그 숫자부터 다시 세는 것이 맞다.
        if (dp[i - 1] + num[i] < num[i]) {
            dp[i] = num[i];
        }
        //아니라면 지금까지의 합을 유지하는 것이 더 좋다.
        else {
            dp[i] = dp[i - 1] + num[i];
        }

        //최고합 저장
        if (dp[i] >= M) {
            M = dp[i];
        }
    }

    cout << M;
}

 

답보다

왜 이렇게 풀었냐?? 어떠한 정당성을 가지고 풀었느냐를 생각해봐야 한다.

 

나는 dp에 그 때까지 수열의 합을 저장하기로 했다.

즉, 수열의 합을 저장하는 과정에서 내가 이 숫자를 저장해야하는가? 를 판단해야한다.

 

10, -4 이면

10은 세고 -4는 세지 않는 것이 맞다.

하지만 10, -12 ,8 이라면 

10,-12, 8 다 세면 6으로 더 작아진다.

 

?? 그럼 안세는 것이 낫다.

즉, 앞서 구한 수열의 합에 이번에 더할 숫자를 더해도 더할 숫자보다 작다면

차라리 더할 숫자부터 다시 세는 것이 낫다는 것이다.

 

이건 알겠지만 그렇다면

가장 중요한 것

왜 처음부터 수열의 합을 구하려고 했나?

사실 경험적으로 알 수 있다

-음수로 시작하면 최댓값이 나올 수 없다.

-작은 값과 큰 값 중 큰 값을 더해야 한다.

 

사실 bruteforce나 다름 없다.

즉, 1~[i+1] 번째까지의 합이 이번에 더할 [i+1]보다 크다면 당연히 처음부터 세는 것이 맞는 것이다.

하지만 이를 저장함으로써 i+1부터 다시 시작할 때 그 전의 값을 이용하게 하기 위함이다.

 

근데 진짜 많이 풀어봐야 할듯.. 나도 시간 좀 걸림. ㅠㅠ