백준 2042 C++ Python 세그먼트 트리 없는 / 사용하지 않은 풀이 (dp 누적합 풀이)

시간 복잡도 O(2억) 

파이썬은 세그먼트 트리를 사용하지 않으면 통과하지 못하지만, C++은 세그먼트 트리를 사용하지 않고 dp 누적합과 간단한 구현만으로 통과가 가능하다. 

 

아래 파이썬 코드를 파이썬 코드로 채점하면, 시간 초과가 나지만, 해당 코드를 C++ 코드로 변경 후 C++로 채점하면 시간 초과가 나지 않는다.

# 이 코드의 시간 복잡도는 O(2억)으로, 파이썬에서는 시간 초과가 난다.

import sys 
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M, K = map(int, input().split())

numberArr = [] 
changedNumberArr = []

for _ in range(N): 
    temp = int(input())
    numberArr.append(temp) # O(100만)

dp = [-1] * (N+1)
dp[0] = 0

def solve(N): # N번째까지의 합
    if N == 1:
        dp[N] = numberArr[0]
        return numberArr[0]
    
    if dp[N] != -1:
        return dp[N]
    
    dp[N] = solve(N-1) + numberArr[N-1] # N까지의 합을 구하려면, N-1 까지의 합과 지금의 N의 값을 더해주면 됨 

    return dp[N]

solve(N) # O(100만)

for i in range(M+K): #O(2만)
    a,b,c = map(int, input().split())
    if a == 1:
        # 중복 제거, 제일 최신 것으로 업데이트 
        isMulti = False 
        for j in range(len(changedNumberArr)): # O(1만)
            A,B,C = changedNumberArr[j] 
            if B == b:
                changedNumberArr[j][1] = b 
                changedNumberArr[j][2] = c
                isMulti = True 
        if not isMulti:
            changedNumberArr.append([a,b,c])

    elif a == 2:        
        # 초기 값을 이용해, 구간의 합을 구한 뒤,
        temp_sum = dp[c]-dp[b-1] # dp 값을 미리 구해두면 시간 복잡도를 더 줄일 수 있음. O(100만)
        # dp 값을 미리 구해둔 ref 값을 사용

        # 1 이었던 리스트를 순회하며 차이를 구한다. 
        gap_sum = 0
        for j in range(len(changedNumberArr)): # O(1만)
            A,B,C = changedNumberArr[j] # B를 C로 바꿨던 것 
            if b <= B <= c:
                gap = abs(numberArr[B-1] - C)
                if numberArr[B-1] >= C:
                    gap *= -1 
                gap_sum += gap
        total_sum = temp_sum + gap_sum
        print(total_sum)

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct UpdateInfo {

    int type; // a

    int index; // b

    long long value; // c

};

int main() {
    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int N, M, K;

    if (!(cin >> N >> M >> K)) return 0;

    vector<long long> numberArr(N);

    vector<UpdateInfo> changedNumberArr;

    for (int i = 0; i < N; i++) {

        cin >> numberArr[i];

    }



    // DP 누적 합 배열 생성

    vector<long long> dp(N + 1, 0);

    for (int i = 1; i <= N; i++) {

        dp[i] = dp[i - 1] + numberArr[i - 1];

    }

    for (int i = 0; i < M + K; i++) {

        int a, b;

        long long c;

        cin >> a >> b >> c;


        if (a == 1) {
            bool isMulti = false;

            for (auto& update : changedNumberArr) {

                if (update.index == b) {

                    update.value = c;

                    isMulti = true;

                    break;

                }

            }

            if (!isMulti) {

                changedNumberArr.push_back({a, b, c});

            }

        }

        else if (a == 2) {

            // 초기 누적 합을 이용해 구간 합 계산
            long long temp_sum = dp[c] - dp[b - 1];

            // changedNumberArr를 순회하며 차이 반영
            long long gap_sum = 0;

            for (const auto& update : changedNumberArr) {

                int B = update.index;

                long long C = update.value;

                if (B >= b && B <= c) {

                    long long gap = C - numberArr[B - 1];

                    gap_sum += gap;

                }

            }

            cout << temp_sum + gap_sum << "\n";

        }

    }



    return 0;

}