반응형

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

 

2015번: 수들의 합 4

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 배열의 1번부터 N번까지 수를 입력받으면서 누적합을 arr 배열에 저장하고, unordered_map<int, long long> um 자료구조에 누적합의 개수를 저장합니다.

 

2. ans에 um[ arr[ i ] - K ] 의 개수를 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
int N, K;
int arr[200001];
unordered_map<int, ll> um;
ll ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K;
 
    um[0] = 1;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        arr[i] += arr[i - 1];
 
        ans += um[arr[i] - K];
 
        um[arr[i]]++;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
[ 백준 ] 3197번 - 백조의 호수 (C++)  (0) 2023.09.24
[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
반응형

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

 

5549번: 행성 탐사

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, sum[ i ][ j ] = sum[ i ][ j - 1 ] + sum[ i - 1 ][ j ] - sum[ i - 1 ][ j - 1 ] + arr[ i ][ j ]를 통해 구간합을 저장합니다.

 

2. 좌표 a, b, c, d를 입력받고,  ans = sum[ c ][ d ] - sum[ a - 1 ][ d ] - sum[ c ][ b - 1 ] + sum[ a - 1 ][ b - 1 ]을 통해 해당 좌표 내의 J, O, 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
45
46
47
48
49
50
51
52
#include<iostream>
#include<string>
 
using namespace std;
 
struct node {
    int J, O, I;
};
 
node sum[1001][1001];
int M, N, K;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M >> N >> K;
 
    for (int i = 1; i <= M; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < N; j++) {
            sum[i][j + 1].J = sum[i][j].J + sum[i - 1][j + 1].J - sum[i - 1][j].J;
            sum[i][j + 1].O = sum[i][j].O + sum[i - 1][j + 1].O - sum[i - 1][j].O;
            sum[i][j + 1].I = sum[i][j].I + sum[i - 1][j + 1].I - sum[i - 1][j].I;
            if (temp[j] == 'J') {
                sum[i][j + 1].J++;
            }
            else if (temp[j] == 'O') {
                sum[i][j + 1].O++;
            }
            else {
                sum[i][j + 1].I++;
            }
        }
    }
 
    for (int i = 0; i < K; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        node ans = { 0 };
 
        ans.J = sum[c][d].J - sum[a - 1][d].J - sum[c][b - 1].J + sum[a - 1][b - 1].J;
        ans.O = sum[c][d].O - sum[a - 1][d].O - sum[c][b - 1].O + sum[a - 1][b - 1].O;
        ans.I = sum[c][d].I - sum[a - 1][d].I - sum[c][b - 1].I + sum[a - 1][b - 1].I;
 
        cout << ans.J << ' ' << ans.O << ' ' << ans.I << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
반응형

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

 

14419번: Foehn Phenomena

Initially, the altitudes of the Spot 0, 1, 2, 3 are 0, 4, 1, 8, respectively. After the tectonic movement on the first day, the altitudes become 0, 6, 3, 8, respectively. At that moment, the temperatures of the wind are 0, -6, 0, -5, respectively.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr 배열에 각 언덕의 높이를 저장하고, diff 배열에 arr[ i ] - arr[ i + 1 ]의 값을 저장합니다.

 

2. L, R, X가 입력되면 diff[ L - 1 ]의 값에 X를 빼주고, R != N일 때 diff[ R ]의 값에 X를 더해줍니다.

 

3. 해당 값을 기준으로 segmentTree를 업데이트해주고, segTree[ 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
59
60
61
62
63
64
65
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, Q, S, T;
ll arr[200001];
ll diff[200000];
ll segTree[400000];
 
void updateTree(int i)
{
    if (diff[i] < 0) {
        segTree[i + N] = diff[i] * S;
    }
    else {
        segTree[i + N] = diff[i] * T;
    }
 
    int temp = i + N;
    temp >>= 1;
    while (temp != 0) {
        segTree[temp] = segTree[temp << 1] + segTree[temp << 1 | 1];
        temp >>= 1;
    }
}
 
int main()
{
    scanf("%d %d %d %d", &N, &Q, &S, &T);
 
    for (int i = 0; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        diff[i] = arr[i] - arr[i + 1];
    }
 
    for (int i = 0; i < N; i++) {
        if (arr[i] < arr[i + 1]) {
            segTree[i + N] = (arr[i] - arr[i + 1]) * S;
        }
        else {
            segTree[i + N] = (arr[i] - arr[i + 1]) * T;
        }
    }
 
    for (int i = N - 1; i >= 1; i--) {
        segTree[i] = segTree[i << 1] + segTree[i << 1 | 1];
    }
 
    for (int i = 0; i < Q; i++) {
        int L, R;
        ll X;
        scanf("%d %d %lld", &L, &R, &X);
 
        diff[L - 1] -= X;
        if(R != N) diff[R] += X;
 
        updateTree(L - 1);
        if (R != N) updateTree(R);
        printf("%lld\n", segTree[1]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
반응형

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

 

11658번: 구간 합 구하기 3

첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 이 문제를 풀기 위해서 2차원 세그먼트 트리를 만듭니다. (segTree [ x ][ y ])

 

2. segTree[ x ]의 리프노드에 x행의 값들을 다시 세그먼트 트리의 형식으로 저장합니다.

 

[출처] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jh20s&logNo=221351546136

 

3. 특정 좌표의 값을 업데이트할 때 x행의 세그먼트 트리 노드를 찾은 후 y열의 세그먼트 트리 노드 값을 바꿔줍니다.

 

4. 구간 합을 구할 때도 3과 마찬가지로 x행의 세그먼트 트리 노드를 찾은 후 y열의 세그먼트 트리 노드의 구간합을 구해줍니다.

 

[ 소스코드 ]

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
78
79
80
81
82
83
84
85
86
#include<iostream>
 
using namespace std;
 
int N, M;
int segTree[2050][2050];
int arr[1025][1025];
 
void updateTreeY(int node, int s, int e, int x, int y, int diff)
{
    if (y < s || e < y) return;
    segTree[x][node] += diff;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTreeY(node * 2, s, m, x, y, diff);
        updateTreeY(node * 2+1, m+1, e, x, y, diff);
    }
}
 
void updateTreeX(int node, int s, int e, int x, int y, int diff)
{
    if (x < s || e < x) return;
    updateTreeY(1, 1, N, node, y, diff);
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTreeX(node * 2, s, m, x, y, diff);
        updateTreeX(node * 2 + 1, m + 1, e, x, y, diff);
    }
}
 
int sumTreeY(int node, int s, int e, int x, int y1, int y2)
{
    if (y2 < s || e < y1) return 0;
    if (y1 <= s && e <= y2) return segTree[x][node];
 
    int m = (s + e) / 2;
    int left = sumTreeY(node * 2, s, m, x, y1, y2);
    int right = sumTreeY(node * 2 + 1, m + 1, e, x, y1, y2);
 
    return left + right;
}
 
int sumTreeX(int node, int s, int e, int x1, int y1, int x2, int y2)
{
    if (x2 < s || e < x1) return 0;
    if (x1 <= s && e <= x2) return sumTreeY(1, 1, N, node, y1, y2);
 
    int m = (s + e) / 2;
    int left = sumTreeX(node * 2, s, m, x1, y1, x2, y2);
    int right = sumTreeX(node * 2 + 1, m + 1, e, x1, y1, x2, y2);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
            updateTreeX(1, 1, N, i, j, arr[i][j]);
        }
    }
 
    for (int i = 0; i < M; i++) {
        int w;
        scanf("%d", &w);
 
        if (w == 0) {
            int x, y, c;
            scanf("%d %d %d", &x, &y, &c);
            int diff = c - arr[x][y];
            arr[x][y] = c;
            updateTreeX(1, 1, N, x, y, diff);
        }
        else {
            int ans = 0;
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            printf("%d\n", sumTreeX(1, 1, N, x1, y1, x2, y2));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 15971번 - 두 로봇 (C++)  (0) 2023.02.10
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 2211번 - 네트워크 복구 (C++)  (0) 2023.02.06
[ 백준 ] 17835번 - 면접보는 승범이네 (C++)  (0) 2023.02.05

+ Recent posts

티스토리툴바