백준 16770번 The Bucket List

백준 16770번 The Bucket List

문제를 푸는 방법이 2가지가 있습니다. 

1. 무식하게 가장 통을 많이 보유하고있는 구간을 탐색하는것

#include <iostream>
#include <string>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int N;
int MaxB;
int visited[1001][1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    int max1 = 0;
    for (int i = 1; i <= N; i++) {
        int a, b,val;
        cin >> a >> b >> val;
        if (max1 < b)
            max1 = b;
        for (int j = a; j <= b; j++) {
            visited[i][j] = val;
        }
    }
    for (int start = 1; start <= max1; start++) {
        int k = 0;
        for (int i = 1; i <= N; i++) {
            k += visited[i][start];
        }
        if (k > MaxB)
            MaxB = k;
    }
    cout << MaxB;
 
 
 
    return 0;
}

2.해당하는 구간이 겹칠때마다 구간의 부분합을 이용해서 푸는 것

#include <iostream>
#include <string>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int N;
int MaxB;
int visited[1001][1001];
int Bucket[1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        int a, b, val;
        cin >> a >> b >> val;
        Bucket[a] += val;
        Bucket[b] -= val;
    }
    
    int ans = 0, cnt = 0;
    for (int i = 0; i <= 1000; i++) {
        cnt += Bucket[i];
        ans = max(ans, cnt);
    }
    cout << ans;
 
 
    return 0;
}

1번 방법이 떠올리기 쉬운 코드이지만 시간복잡도는 O(n^2)인 반면, 2번 방법으로 풀었을때 좀더 최적화된 좋은 코드입니다.