1912. 연속합

1. 시간 초과된 풀이

문제풀이 : 

1)  DP[] 배열에 choose 개의 연속된 수의 합을 저장했다. 그리고 N[] 배열에 입력받은 수열을 저장했다.

2) DP[] 배열은 choose 의 값에 따라 저장되는 값이 달라진다.

3) choose = 1 일 때의 DP[] 배열은 N[] 배열과 동일하다. DP[i] = N[i]

4) choose = 2 일 때의 DP[] 배열은 DP[i] = N[i] + N[i+1] 이다. 즉, DP[i] = (choose = 1 일 때의 DP[i]) + N[i+1]

5) choose = 3 일 때의 DP[] 배열은 DP[i] = N[i] + N[i+1] + N[i+2] 이다. 즉, DP[i] = (choose = 2 일 때의 DP[i]) + N[i+2]

6) 정리하자면, (choose = N 일 때의 DP[i]) = (choose = N-1 일 때의 DP[i]) + N[i + choose]

    예를들자면, choose = 2 일 때의 DP[] 와 choose = 3 일 때의 DP[] 를 비교해 보자

7) vscode 에서 예제대로 입력했을 때, 정답이 출력되었다. ☞즉, 백준 기준 제한시간(1초) 내에 계산되지 못한 것이다.

	choose = 2	choose = 3
i = 0	N[0] + N[1]	N[0] + N[1] (= DP[0])+ N[2]
i = 1	N[1] + N[2]	N[1] + N[2] (= DP[1])+ N[3]
i = 2	N[2] + N[3]	N[2] + N[3] (= DP[2])+ N[4]
i = 3	N[3] + N[4]

 

시간초과 이유:

백준에서 시간 초과된 이유를 고민해봤다.

1) n의 최대값인 100000의 경우를 생각해보면, 제한시간(1초) 내에 실행완료되지 않는다.

2) 빅오표기법으로 시간복잡도를 계산해봤다.

    내가 작성한 코드는 O(100000^2) 의 시간복잡도를 갖는다. 보통 n = 10000 일 때 O(n^2) 는 1초의 시간이 걸린다고 한다.     

3) 따라서, O(100000^2) 는 제한시간(1초) 내에 실행되지 않는다.

 

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAX 100000
#define endl "\n"

using namespace std;

int n;
long long N[MAX];
long long DP[MAX];

void Input()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> N[i];
    }
}

void Initial()
{
    memset(DP, 0, sizeof(DP));
}

void Solution()
{
    long long sum = 0;
    long long maxSum = -2000;
    for(int choose = 1; choose <= n; choose++)
    {
        for (int i = 0; i <= n - choose; i++)
        {
            sum = DP[i] + N[i + choose - 1];


            DP[i] = sum;
            maxSum = max(maxSum, sum);
        }
    }

    cout << maxSum << endl;
}

int main()
{
    Input();
    Initial();
    Solution();

    return 0;
}

 

2. 해결방법

 

3. Solution