반응형

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

 

5430번: AC

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 값들을 입력받고, 전처리를 통해서 배열의 값들을 deque에 넣어줍니다.

 

2. R이 입력되면 rev변수를 갱신해 줍니다.

 

3. rev변수의 값에 따라 pop_back, 혹은 pop_front를 해줍니다.

 

4. deq에 남아있는 수를 rev변수에 따라 출력해 줍니다.

 

[ 소스코드 ]

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
87
88
89
90
#include<iostream>
#include<deque>
#include<string>
 
using namespace std;
 
int T;
deque<int> deq;
 
void preproc(string x)
{
    int num = 0;
    for (auto next : x) {
        if (next >= '0' && next <= '9') {
            num *= 10;
            num += next - '0';
        }
        else if (next == ']' || next == ',') {
            deq.push_back(num);
            num = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        bool flag = true;
        bool rev = false;
        deq.clear();
        string p, x;
        int n;
        cin >> p >> n >> x;
 
        if (n) preproc(x);
 
        for (auto com : p) {
            if (com == 'R') {
                rev = !rev;
            }
            else {
                if (!deq.empty()) {
                    if (rev) {
                        deq.pop_back();
                    }
                    else {
                        deq.pop_front();
                    }
                }
                else {
                    cout << "error\n";
                    flag = false;
                    break;
                }
            }
            
        }
 
        if (flag) {
            cout << '[';
            while (!deq.empty()) {
                if (rev) {
                    if (deq.size() == 1) {
                        cout << deq.back();
                    }
                    else {
                        cout << deq.back() << ',';
                    }
                    deq.pop_back();
                }
                else {
                    if (deq.size() == 1) {
                        cout << deq.front();
                    }
                    else {
                        cout << deq.front() << ',';
                    }
                    deq.pop_front();
                }
            }
            cout << "]\n";
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
[ 백준 ] 3151번 - 합이 0 (C++)  (0) 2023.07.10
[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08
[ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++)  (0) 2023.07.07
[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
반응형

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

 

6198번: 옥상 정원 꾸미기

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, 건물의 높이 h의 값이 stack.top보다 크거나 같을 경우 st.pop을 해주고, st이 완전히 비기 전까지 반복해줍니다.

 

2. cnt에 현재 st의 size를 더해줍니다. 이때, cnt의 최댓값이 약 32억이므로 자료형을 long long으로 선언해줍니다.

 

3. stack에 건물의 높이 h를 push합니다.

 

4. cnt를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
#define ll long long
 
using namespace std;
 
int N;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    stack<int> st;
 
    ll cnt = 0;
 
    for (int i = 0; i < N; i++) {
        int h;
        cin >> h;
 
        if (i == 0) {
            st.push(h);
        }
        else {
            while (st.top() <= h) {
                st.pop();
                if (st.empty()) break;
            }
 
            cnt += st.size();
            st.push(h);
        }
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5430번 - AC (C++)  (0) 2023.07.09
[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08
[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
반응형

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

 

1863번: 스카이라인 쉬운거

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, stack.top의 값이 현재 값보다 클 경우 cnt++, s.pop을 해주고, 같을 경우는 s.pop만 해줍니다.

 

2. stack에 y를 push합니다.

 

3. 위 과정이 끝난 후 마지막에 1번 과정을 반복해줍니다.

 

4. cnt를 출력합니다.

 

[ 소스코드 ]

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>
#include<stack>
 
using namespace std;
 
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    stack<int> s;
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
 
        while (!s.empty() && s.top() >= y) {
            if (s.top() != y) cnt++;
            s.pop();
        }
 
        s.push(y);
    }
 
    while (!s.empty() && s.top() >= 0) {
        if (s.top() != 0) cnt++;
        s.pop();
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01
[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30
[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
반응형

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

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열이 trie에 있는지 체크하고, 있다면 NO를 출력하고, 그렇지 않다면 YES를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, t;
 
struct trie {
    trie* num[10];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) num[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete num[i];
        }
    }
 
    void insert(const char* ch) {
        if (!*ch) {
            this->end = true;
            return;
        }
 
        int now = *ch - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(ch + 1);
    }
 
    bool find(const char* ch) {
        if (!*ch || end) {
            return true;
        }
 
        int now = *ch - '0';
        if (!num[now]) return false;
        return num[now]->find(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--) {
        trie* root = new trie;
        bool flag = true;
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            char arr[11];
            cin >> arr;
 
            if (root->find(arr)) {
                if(flag) cout << "NO\n";
                flag = false;
            }
            else {
                root->insert(arr);
            }
        }
 
        if (flag) {
            cout << "YES\n";
        }
 
        delete root;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.21
반응형

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

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. queue를 만들어 카드를 뽑고 다시 넣는 행동을 반복하다가 queue의 사이즈가 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int main()
{
    int N;
    cin >> N;
 
    queue<int> q;
 
    for (int i = 1; i <= N; i++) {
        q.push(i);
    }
 
    while (q.size() != 1) {
        q.pop();
        int temp = q.front();
        q.pop();
        q.push(temp);
    }
 
    cout << q.front();
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5022번 - 연결 (C++)  (1) 2023.06.19
[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18
[ 백준 ] 14497번 - 주난의 난(難) (C++)  (0) 2023.06.16
[ 백준 ] 10464번 - XOR (C++)  (0) 2023.06.15
[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
반응형

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

 

14463번: 소가 길을 건너간 이유 9

첫 줄에 N (1 ≤ N ≤ 50,000)이 주어진다. 다음 2N줄에는 한 줄에 하나씩 길 위의 점을 지나간 소의 번호가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. visited 배열을 선언하고, 소가 나오면 해당 위치를 visited 배열에 저장하고, 해당 위치의 Segment Tree 노드에 1을 더해줍니다.

 

2. 만약 입력받은 수가 이미 방문을 했다면 visited[ n ] + 1 ~ i - 1 까지의 구간합을 ans에 더해주고, visited[ n ]의 Segment Tree 노드에 -1을 해줍니다.

 

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
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
#include<iostream>
 
using namespace std;
 
int N;
int visited[50001];
int segTree[200000];
 
void updateTree(int idx, int diff)
{
    while (idx != 0) {
        segTree[idx] += diff;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
 
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    int ans = 0;
 
    for (int i = 1; i <= 2 * N; i++) {
        int a;
        scanf("%d", &a);
 
        if (visited[a] == 0) {
            visited[a] = i;
            updateTree(2 * N + i - 1, 1);
        }
        else {
            ans += getTree(2 * N + visited[a], 2 * N + i - 2);
            updateTree(2 * N + visited[a] - 1, -1);
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 12919번 - A와 B 2 (C++)  (0) 2023.06.12
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
반응형

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

 

5817번: 고통받는 난쟁이들

옛날 옛적, 일곱 언덕과 일곱 바다를 건너 작은 마을이 있었어요. 백설공주는 놀고 먹고 자다가 일어나서 문명 5, 리그 오브 레전드, 풋볼 매니저를 하다가 다시 자는 난쟁이들 N명과 살고 있었어

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 난쟁이들의 키를 입력 받고, 난쟁이들의 키를 인덱스로, 난쟁이들의 위치를 값으로하는 세그먼트 트리를 만듭니다.

 

2. 각 노드에는 구간의 최댓값과 최솟값을 각각 저장합니다.

 

3. 해당 구간의 최댓값과 최솟값의 차이가 Y - X와 같다면 YES를 아니라면 NO를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
pair<int,int> segTree[524444];
int arr[200000];
int Min, Max;
 
void updateTree(int node, int s, int e, int idx, int n)
{
    if (idx < s || e < idx) return;
    if (s == e) {
        segTree[node] = { n, n };
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, idx, n);
    updateTree(node * 2 + 1, m + 1, e, idx, n);
 
    segTree[node].first = max(segTree[node * 2].first, segTree[node * 2 + 1].first);
    segTree[node].second = min(segTree[node * 2].second, segTree[node * 2 + 1].second);
}
 
void getTree(int node, int s, int e, int sidx, int eidx)
{
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        Min = min(Min, segTree[node].second);
        Max = max(Max, segTree[node].first);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, sidx, eidx);
    getTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        updateTree(1, 1, N, arr[i], i);
    }
 
    for (int i = 0; i < M; i++) {
        int cmd, X, Y;
        scanf("%d %d %d", &cmd, &X, &Y);
 
        if (cmd == 1) {
            updateTree(1, 1, N, arr[Y], X);
            updateTree(1, 1, N, arr[X], Y);
            swap(arr[X], arr[Y]);
        }
        else {
            Min = 987654321;
            Max = 0;
            getTree(1, 1, N, X, Y);
 
            if (Y - X == Max - Min) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12919번 - A와 B 2 (C++)  (0) 2023.06.12
[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
반응형

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

 

14449번: Balanced Photo

The first line of input contains N. The next N lines contain h1…hN, each a nonnegative integer at most 1,000,000,000.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. arr 배열에 키를 저장하고, vector<int> h에 입력으로 주어진 모든 키를 push 합니다.

 

2. h를 오름차순으로 정렬합니다.

 

3. 0부터 N - 1까지 arr 배열을 돌면서 해당 값의 idx를 lower_bound를 통해 구합니다.

 

4. idx + 1 ~ e * N - 1의 구간합을 통해 왼쪽에 있는 값들 중 큰 값을 구하고, cntL에 저장합니다.

 

5. N - 1부터 0까지 위의 3, 4와 같은 방식으로 구하고 cntR에 구간합을 저장합니다.

 

6. cntL[ i ] * 2 < cntR[ i ] 이거나 cntL[ i ] > cntR[ i ] * 2이면 ans++를 해줍니다.

 

7. 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
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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[100000];
int cntL[100000];
int cntR[100000];
int segTree[200000];
vector<int> h;
int ret;
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
        
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        h.push_back(arr[i]);
    }
 
    sort(h.begin(), h.end());
 
    for (int i = 0; i < N; i++) {
        auto idx = lower_bound(h.begin(), h.end(), arr[i]) - h.begin();
        updateTree(idx + N);
 
        cntL[i] = getTree(N + idx + 1, 2 * N - 1);
    }
 
    fill(segTree, segTree + 2 * N, 0);
 
    for (int i = N - 1; i >= 0; i--) {
        auto idx = lower_bound(h.begin(), h.end(), arr[i]) - h.begin();
        updateTree(idx + N);
 
        cntR[i] = getTree(N + idx + 1, 2 * N - 1);
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        int L = cntL[i];
        int R = cntR[i];
 
        if (L > R) {
            swap(L, R);
        }
 
        if (2 * L < R) ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
반응형

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

 

11962번: Counting Haybales

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 세그먼트 트리를 업데이트 해줍니다.

 

2. 구간 합과 구간 최솟값을 각각 저장해 쿼리에 맞게 출력해줍니다.

 

[ 소스코드 ]

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#define ll long long
 
using namespace std;
 
struct node {
    ll sum;
    ll min;
};
 
int N, Q;
int arr[200001];
node segTree[524300];
ll lazy[524300];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node].sum += lazy[node] * (1LL * e - s + 1);
        segTree[node].min += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
 
    return;
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node].sum = 1LL * arr[s];
        segTree[node].min = 1LL * arr[s];
 
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int C)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node].sum += (1LL * e - s + 1) * (1LL * C);
        segTree[node].min += C;
 
        if (s != e) {
            lazy[node * 2] += C;
            lazy[node * 2 + 1] += C;
        }
 
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, C);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, C);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
ll getSum(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node].sum;
 
    int m = (s + e) / 2;
    
    return getSum(node * 2, s, m, sidx, eidx) + getSum(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
ll getMin(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 11111111111;
    if (sidx <= s && e <= eidx) return segTree[node].min;
 
    int m = (s + e) / 2;
 
    return min(getMin(node * 2, s, m, sidx, eidx), getMin(node * 2 + 1, m + 1, e, sidx, eidx));
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        char cmd;
        int A, B;
        cin >> cmd >> A >> B;
 
        if (cmd == 'M') {
            cout << getMin(1, 1, N, A, B) << '\n';
        }
        else if (cmd == 'P') {
            int C;
            cin >> C;
 
 
            updateTree(1, 1, N, A, B, C);
        }
        else {
            cout << getSum(1, 1, N, A, B) << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
반응형

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

 

15816번: 퀘스트 중인 모험가

첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. list 배열에 완료한 퀘스트를 저장하고, vector<int> quest에 입력으로 주어진 모든 퀘스트 항목들을 push 하고 중복을 제거합니다.

 

2. for문으로 arr배열을 돌면서 lower_bound를 활용하여 해당 퀘스트가 몇번 째 순서인지 확인하고, segmentTree를 업데이트해줍니다.

 

3. query를 이용하여 R - L + 1 - (L ~ R 구간합)을 통해 답을 출력합니다.

 

[ 소스코드 ]

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct query {
    int cmd;
    int L, R;
};
 
int N, M;
vector<int> quest;
query arr[1000000];
int segTree[6000000];
int list[1000000];
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
 
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int Q;
        scanf("%d", &Q);
 
        list[i] = Q;
        quest.push_back(Q);
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int X;
            scanf("%d", &X);
 
            quest.push_back(X);
            arr[i] = { cmd,X,0 };
        }
        else {
            int L, R;
            scanf("%d %d", &L, &R);
 
            quest.push_back(L);
            quest.push_back(R);
            arr[i] = { cmd,L,R };
        }
    }
 
    sort(quest.begin(), quest.end());
    quest.erase(unique(quest.begin(), quest.end()), quest.end());
    int n = quest.size();
 
    for (int i = 0; i < N; i++) {
        auto idx = lower_bound(quest.begin(), quest.end(), list[i]) - quest.begin();
        updateTree(n + idx);
    }
 
    for (int i = 0; i < M; i++) {
        int cmd = arr[i].cmd;
        int L = arr[i].L;
        int R = arr[i].R;
 
        if (cmd == 1) {
            auto idx = lower_bound(quest.begin(), quest.end(), L) - quest.begin();
            updateTree(n + idx);
        }
        else {
            auto Lidx = lower_bound(quest.begin(), quest.end(), L) - quest.begin();
            auto Ridx = lower_bound(quest.begin(), quest.end(), R) - quest.begin();
 
            printf("%d\n", R - L + 1 - getTree(n + Lidx, n + Ridx));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04

+ Recent posts

티스토리툴바