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


MST를 구현해주면 되고, 크루스칼 알고리즘을 이용한다.


크루스칼 알고리즘은 유니온 파인드를 그대로 옮겨 놨다고 봐도 상관이 없다.


0. 유니온 파인드를 활용하기 때문에, 최상위 부모노드의 값을 자기 자신으로 초기화한다.


1. 간선 정보를 비용 오름차순으로 정렬한다.


2. 간선의 시작점과 끝점을 union해보면서, 같은 그룹에 속해있지 않다면, union 해주고 간선 비용을 추가해준다.

이미 같은 그룹이라면 연결되어 있다는 의미이기 때문에 비용에 더해주지 않고 스킵한다.


3. 모든 노드를 연결하는데에 필요한 간선의 개수는 n-1개이다. 따라서 n-1개 만들었으면 그만두고 반복문을 빠져나오자.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int n, e, r[10002];
struct EDGE {
    int from, to, cost;
};
vector<EDGE> edge;
bool cmp(EDGE a, EDGE b) {
    return a.cost < b.cost;
}
int getParent(int a) {
    if (r[a] == a) return a;
    else return r[a] = getParent(r[a]);
}
bool join(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) return false; //이미 연결되어 있음
    else if (a < b)
        r[b] = a;
    else
        r[a] = b;
    return true;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> e;
 
    while (e--) {
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge.push_back({ src, dst, cost });
    }
    sort(edge.begin(), edge.end(), cmp);
 
    for (int i = 1; i <= n; i++)
        r[i] = i;
 
    //연결 안 되어 있는 노드 찾아서 연결 해보고, 연결 안 되어 있으면 연결하고 비용 추가
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < edge.size(); i++) {
        if (join(edge[i].from, edge[i].to)) {
            res += edge[i].cost;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    printf("%lld ", res);
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 11438 LCA2 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15

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



각 단계별로 시간(비용)이 있을 때, 위상 정렬을 할 수 있는 정보가 주어지는 경우이다.


입력을 받을 때, indegree를 모두 구하면서 입력을 받는다.


초기에 indegree가 0인 지점을 큐에 넣고 시작하는데, 이런 지점은 이전에 필요로 하는 단계가 없기 때문에, 그 지점의 비용이


그 지점까지 총 비용이 된다.



이후에는 위상 정렬을 진행하는데, 현재 단계까지의 총 비용은 확정이므로, 다음 단계의 총 비용을 구해준다. 이 때, 시간의 경우, 가장 오래걸리는 시간을 넣어줘야 한다.


이게 당연한 것이, 4번을 수행하기 위해 1번과 3번을 사전에 수행해야 한다고 해보자.


다른 조건이 없다는 가정하에, 1번과 3번중에서는 어떤 것을 먼저해도 상관이 없다.


그렇다면 예를들어 1번을 하는데에 3초가 걸리고, 3번을 하는데에 6초가 걸린다고 쳐보자. 그리고 4번만을 수행하는 데에는 5초가 걸린다고 하자.


1번을 볼 때, 1번 다음에 4번을 수행해야 한다는 것을 알고 있고, 이 시점에서 4번을 완수하기 위해서는 1번의 시간 + 4번의 시간이 필요하다.


1번을 하면서 동시에 3번도 수행할 수 있기 때문에, 앞서 구한 1번 시간 + 4번시간과 3번 시간 + 4번시간을 비교해서, 오래 걸리는 시간으로 갱신해줘야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
int t[502], n, ind[502], done[502];
vector<int> v[502];
queue<int> q;
 
void tpgSort() {
    for (int i = 1; i <= n; i++)
        if (ind[i] == 0) {
            q.push(i);
            done[i] = t[i];
        }
 
    for (int i = 0; i < n; i++) {
        if (q.empty()) cout << "cycle\n";
 
        int cur = q.front();
        q.pop();
        
            int Max = -1;
            for (int j = 0; j < v[cur].size(); j++) {
                ind[v[cur][j]]--;
                if (ind[v[cur][j]] == 0) q.push(v[cur][j]);
                //다음 단계 비용 = 현재 단계까지 총비용중 가장 오래걸리는 비용 + 다음 단계 비용
                if (done[v[cur][j]] < done[cur] + t[v[cur][j]]) {
                    done[v[cur][j]] = done[cur] + t[v[cur][j]];
                }
            }
 
    }
}
int main(void) {
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int time;
        cin >> time;
        t[i] = time;
        while (1) {
            int pre;
            cin >> pre;
            if (pre == -1) break;
            v[pre].push_back(i);
            ind[i]++;
        }
    }
    tpgSort();
    for(int i = 1 ; i <= n ; i++ )
        printf("%d\n", done[i]);
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11438 LCA2 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15

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


dp느낌으로 해결이 가능하다. . 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다


이 문장때문에 아래 풀이로 가능한 것이다.


d[i] = i의 사전작업까지 모두 포함해서 작업 i를 끝내는 데에 걸리는 시간


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, t[10001], d[10001];
vector<int> v[10001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tm, num;
        cin >> tm >> num;
        t[i] = tm;
        while (num--) {
            int pre;
            cin >> pre;
            v[i].push_back(pre);
        }
    }
    //d[i] = i의 사전작업까지 다 포함해서 작업 i 끝내는데 드는 시간
    d[1] = t[1];
    for (int i = 2; i <= n; i++) {
        if (v[i].size() == 0) d[i] = t[i]; //사전 작업 없으면 그 작업 끝내는 시간
        else {
            int Max = -1;
            for (int j = 0; j < v[i].size(); j++) {
                if (Max < d[v[i][j]]) Max = d[v[i][j]];
            }
            d[i] = Max + t[i];
        }
    }
    //어떤 작업이 제일 마지막에 끝날지는 알 수 없지만, 필요 시간이 가장 긴게 마지막에 끝나는 것
    int ret = -1;
    for (int i = 1; i <= n; i++)
        if (ret < d[i]) ret = d[i];
    cout << ret;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14

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


풀어야할 문제들이 난이도로 주어진다. 또한 어떤 문제를 어떤 문제보다 먼저 풀어야한다는 식의 데이터가 주어지므로, 위상 정렬을 활용한다.


다만 큐에서 꺼낼때, 난이도가 낮은 문제를 먼저 꺼내야 하기 때문에, min heap을 사용해주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
priority_queue<int, vector<int>, greater<int> > q;
void tpgSort() {
    for (int i = 1; i <= n; i++) { //indegree 0인거 큐에 넣고 시작
        if (ind[i] == 0) q.push(i);
    }
 
    for (int i = 0; i < n; i++) { // 노드의 개수보다 더 많이 돌면 사이클
        if (q.empty()) cout << "cycle occured\n";
 
        int cur = q.top(); q.pop();
        cout << cur << ' '; //노드 삭제
 
        
        for (int i = 0; i < v[cur].size(); i++) {
            ind[v[cur][i]]--; //삭제된 노드와 연결된 간선 제거
            if (ind[v[cur][i]] == 0) q.push(v[cur][i]);
        }
 
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    tpgSort();
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14

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


뭐의 앞에 뭐가 오고, 뭐의 앞엔 뭐가 온다 이런 형태로 정보가 주어지면 위상 정렬을 수행한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
queue<int> q;
void tpgSort() {
    for (int i = 1; i <= n; i++) { //indegree 0인거 큐에 넣고 시작
        if (ind[i] == 0) q.push(i);
    }
 
    for (int i = 0; i < n; i++) { // 노드의 개수보다 더 많이 돌면 사이클
        if (q.empty()) cout << "cycle occured\n";
 
        int cur = q.front(); q.pop();
        cout << cur << ' '; //노드 삭제
 
        
        for (int i = 0; i < v[cur].size(); i++) {
            ind[v[cur][i]]--; //삭제된 노드와 연결된 간선 제거
            if (ind[v[cur][i]] == 0) q.push(v[cur][i]);
        }
 
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    tpgSort();
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14

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


유니온 파인드를 단순히 적용하면 TLE를 맞는 문제이다.


따라서 배열에 지속적으로 그룹의 크기를 저장해줘야 하는데, 따라서 일관성을 가지도록 union함수를 구현해줘야한다.


무조건 작은 값이 부모가 되도록 하는 것이다.



처음에는 단순하게 주석 처리된 부분으로 제출해서 TLE를 맞았다. 가장 단순하게 할 수 있는 해결법이, 쿼리를 진행하기 전에,


모든 원소에 대해서 부모 검색을 다시 수행해서 제대로 된 부모들을 찾아두는 것인데, 이 방법을 사용할 수 없다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<map> //찾는 게 없으면 0반환
#include<string>
#include<algorithm>
using namespace std;
map<string, int> mp;
 
int r[200002], fcnt[200002];
 
int getParent(int a) {
    if (r[a] == a) return r[a];
    else
        return r[a] = getParent(r[a]);
}
int join(int a, int b) {
    
    a = getParent(a);
    b = getParent(b);
    if (a < b) {
        r[b] = a;
        fcnt[a] += fcnt[b];
        fcnt[b] = 1;
        return fcnt[a];
    }
    else if (a > b) {
        r[a] = b;
        fcnt[b] += fcnt[a];
        fcnt[a] = 1;
        return fcnt[b];
    }
    return fcnt[b];
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int idx = 0;
        for (int i = 0; i < 2 * n; i++) {
            r[i] = i;
            fcnt[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            string fir, sec;
            cin >> fir >> sec;
 
            if (mp.count(fir) == 0) {
                mp.insert({ fir, idx });
                idx++;
            }
            if (mp.count(sec) == 0) {
                mp.insert({ sec, idx });
                idx++;
            }
            
            cout << join(mp[fir], mp[sec]) << '\n';
            
            //for (int i = 1; i < idx; i++) getParent(i);
 
            //int cnt = 0;
            //for (int i = 0; i < idx; i++)
            //    if (r[i] == r[mp[fir]])
            //        cnt++;
            //cout << cnt << '\n';
        
        }
        mp.clear();
        
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14

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


유니온파인드를 활용하는 문제이다.


주의할 점은, 항상 특정 노드의 최상위 부모가, 업데이트가 되어있지 않을 수 있다는 생각을 하고, 구현을 해야한다는 것이다.


따라서 최상위 부모를 찾으러 올라갈 때도, 항상 getParent 함수를 호출하면서 올라간다.


마찬가지로 union연산을 할 때에도, a혹은 b의 최상위 부모가 제대로 갱신이 되어있지 않을 수 있기 때문에 마찬가지로 갱신을 하면서 찾아준다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
int r[1000002], n;
 
int getParent(int a) {// 마찬가지로 갱신하면서 찾으러 올라감
    if (r[a] == a) return r[a];
    else return r[a] = getParent(r[a]);
}
 
void join(int a, int b) { //갱신하면서
    r[getParent(a)] = getParent(b); //a의 부모를 b의 부모로 update 한다
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++)
        r[i] = i;
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0)
            join(a, b);
        else if (cmd == 1) {
            //for (int i = 0; i <= n; i++) getParent(i);
            int pa = getParent(a);
            int pb = getParent(b);
            if (pa == pb) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14

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


그래프 정보를 배열로 받아주고, DFS를 돌려주면 된다.


DFS를 실행할 때, 방문한 지점을 다시 방문하는 것이 base condition이므로, DFS가 끝날 때 마다 사이클의 개수가 하나씩 늘어난다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<vector>
using namespace std;
int v[1002];
bool vis[1002];
 
void dfs(int cur) {
    if (vis[cur]) return; //이미 방문한 곳을 재방문 했다는 건 사이클이라는 뜻
 
    vis[cur] = true;
    int next = v[cur];
    dfs(next);
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        
        for (int i = 1; i <= n; i++) 
            cin >> v[i];
        
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && v[i] != 0) {
                cnt++;
                dfs(i);
            }
        }
        cout << cnt << '\n';
 
        for (int i = 1; i <= n; i++) 
            vis[i] = false;
        
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14

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


인덱스 트리를 활용하여 해결했다.


앞선 인덱스 트리를 활용하는 문제들과 같이, 이 문제도 말만 다르지, 결국 원소 업데이트가 빈번하게 일어나는 동시에 구간합을 구하는 문제이다.


특정 맛의 사탕을 빼거나 더하는 것은, 인덱스 트리의 기본적인 업데이트 쿼리와 동일하기 때문에 따로 설명하지는 않을 것이고, 특정 순위의 사탕을 가져오는 부분에 대해서만 살펴보겠다.



a == 1인 경우에 k번째 순위를 가지는 사탕을 가져와야 하는 상황이다.


root에서부터 노드 하나하나가 사탕의 개수를 구간합으로 가지고 있는 형태로 트리를 만들어준다. leaf 노드의 수는 가능한 맛의 범위로 잡아주면 된다. 이 문제에서는 100 만이었던 것으로 기억한다.


이렇게 leaf 노드는 그 맛의 사탕이 몇 개 있다는 것을 의미한다.



이제 k번째 순위의 사탕을 찾는다고 하면, 트리의 왼쪽에서부터(가장 맛있는 사탕부터) k번째인 것이다. 이때 k보다 한 노드의 값(거기까지 구간합)이 크다면 그 노드의 자손 부분에 우리가 찾는 k번째 사탕이 존재한다는 의미이므로 계속 아래로 내려가준다.


반대로 k보다 작다면, 우리가 찾는 k번째 사탕이 그 노드의 오른쪽 트리에 있다는 것이기 때문에 오른쪽으로 이동해주고, 왼쪽에 있는 사탕의 개수(확인했던 구간합의 값)만큼 k를 감소시켜준다.


또한 리트 노드에 도달했다면 위의 작업을 해줄 필요가 없기 때문에, 리프 노드인지 아닌지 확인해 주는 작업을 함께 진행해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#define MAX 1000000
using namespace std;
 
int idxT[4 * MAX+2], start = 1;
 
void Update(int idx, int delta) {
    while (idx > 0) {
        idxT[idx] += delta;
        idx /= 2;
    }
}
 
int getCandy(int k) {
    int i = 1;
    while (1) {
        if (idxT[i] >= k) { //이 지점의 서브트리에 우리가 찾는 사탕이 속해 있다면
            if (i >= start && i < start + MAX) { //그 지점이 leaf라면 종료
                Update(i, -1);
                return i - start + 1;
            }
            i *= 2; //leaf가 아니라면 이어서 탐색
            continue;
        }
        else { //이 지점이 아닌 반대쪽에 우리가 찾는 사탕이 있다면
            k = k - idxT[i]; 
            i++;
            continue;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    while (start < MAX) //MAX보다 크거나 같으면서 가장 큰 2의 제곱수
        start *= 2;
    
    int n; 
    cin >> n; //쿼리의 수
    for (int i = 0, a, b, c ; i < n; i++) {
        cin >> a >> b;
        if (a == 1) 
            cout << getCandy(b) << '\n'; //사탕 꺼내기
        
        else {
            cin >> c; //사탕의 변화량
            Update(b + start - 1, c);
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13

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


수열의 성분이 빈번하게 바뀌면서, 구간합을 물어보는 문제이기 때문에 인덱스 트리를 구현해주면 된다.


인덱스 트리에 대한 좀 더 자세한 설명은 https://hugssy.tistory.com/132 를 참고하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll idxTree[4 * 100002];
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    int start = 1;
    while (start < n)
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
 
    for (int i = 0; i < n; i++)
        cin >> idxTree[i + start];
 
    for (int i = start - 1; i >= 1; i--)
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
 
    while (q--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if (x > y) swap(x, y);
        cout << findSum(x + start - 1, y + start - 1) << '\n';
        Update(a + start - 1, b - idxTree[a + start - 1]);
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13

+ Recent posts

티스토리툴바