BOJ 1912 연속합

문제 바로가기

문제

반성할 점

요즘 너무 이론적인 것과 형식에 치우쳤는지 DP 하면 그냥 일단 필요한 것들을 쳐놓고 시작했다.
문제집을 만들어놓고 푼 것과 LIS에 너무 집착한 것도 한 몫을 한것같다.
이런 행동이 시야를 좁혔고, 엄청 간단한 문제임에도 구현을 바로 하지 못하고 헤매었다.
직관적으로 코드를 짜기 위해 재귀로 DP 푸는것을 선택했는데, 오히려 자신을 어렵게 하고 있었다.
이런 점을 반성하며, 앞으로 내 형식과 과정을 갖는데에도 신경을 써야겠다고 생각했다.

잘한 점

'세그먼트 트리' 라는 알고리즘을 얼마전에 주워듣고는 적용을 시도했고, 원하는 대로 구현했다.

코드

// 2021.09.25 22:00:13
// 1912 https://boj.kr/1912
#include <bits/stdc++.h>
using namespace std;

vector<int> s;
int dp[100001];
int f(int pos)
{
    if (pos >= s.size())
        return 0;
    int &ret = dp[pos];
    if (ret != -987654321)
        return ret;
    int addNext = f(pos + 1) + s[pos];
    int stop = s[pos];
    return ret = max(addNext, stop);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        s.push_back(temp);
        dp[i] = -987654321;
    }

    int best = -987654321;
    for (int i = 0; i < n; i++)
    {
        best = max(best, f(i));
    }
    cout << best;
}

결과