반응형

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

 

19591번: 독특한 계산기

숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받을 str 변수를 선언하고, 입력을 받습니다.

 

2. num을 선언하고, 기호가 아닌 문자가 나오면 num = num * 10 + str[ i ] - '0'을 통해 num을 갱신해 줍니다.

 

3. 기호가 나온다면 deque<char> symbol에 기호를 push_back 해주고, 첫 번째 문자열이 '-'라면 isFirst를 true로 바꾸고, num의 값에 -1을 곱해준 후 deque<ll> number에 num을 push_back 해줍니다.

 

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
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<iostream>
#include<deque>
#include<string>
#define ll long long
 
using namespace std;
deque<ll> number;
deque<char> symbol;
ll ans;
 
ll cal(ll num1, ll num2, char sym)
{
    if (sym == '+') {
        return num1 + num2;
    }
    else if (sym == '-') {
        return num1 - num2;
    }
    else if (sym == '*') {
        return num1 * num2;
    }
    else {
        return num1 / num2;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string str;
 
    cin >> str;
 
    bool isFirst = false;
    ll num = 0;
 
    for (int i = 0; i < str.size(); i++) {
        if (i == 0 && str[i] == '-') {
            isFirst = true;
        }
        else if (str[i] >= '0') {
            num = num * 10 + str[i] - '0';
        }
        else {
            if (isFirst) {
                isFirst = false;
                num *= -1;
            }
            number.push_back(num);
            symbol.push_back(str[i]);
            num = 0;
        }
    }
    if (isFirst) {
        isFirst = false;
        num *= -1;
    }
    number.push_back(num);
 
    if (number.size() == 1) {
        cout << number.front();
        return 0;
    }
 
    while (1) {
        ll tmp[4] = { 0 };
 
        if (number.size() == 3) {
            tmp[0] = number.front();
            tmp[3] = number.back();
            number.pop_back();
            number.pop_front();
            tmp[1] = tmp[2] = number.front();
        }
        else if (number.size() == 2) {
            tmp[0] = number.front();
            tmp[1] = number.back();
        }
        else {
            tmp[0] = number.front();
            tmp[3] = number.back();
            number.pop_back();
            number.pop_front();
            tmp[1] = number.front();
            tmp[2] = number.back();
        }
 
        if (symbol.size() == 1) {
            char sym = symbol.front();
            cout << cal(tmp[0], tmp[1], sym);
 
            return 0;
        }
        else {
            char sym1 = symbol.front();
            char sym2 = symbol.back();
 
            if (sym1 == '+' || sym1 == '-') {
                if (sym2 == '*' || sym2 == '/') {
                    symbol.pop_back();
                    number.pop_back();
                    number.push_back(cal(tmp[2], tmp[3], sym2));
                    number.push_front(tmp[0]);
                }
                else {
                    ll num1 = cal(tmp[0], tmp[1], sym1);
                    ll num2 = cal(tmp[2], tmp[3], sym2);
 
                    if (num1 >= num2) {
                        symbol.pop_front();
                        number.pop_front();
                        number.push_front(cal(tmp[0], tmp[1], sym1));
                        number.push_back(tmp[3]);
                    }
                    else {
                        symbol.pop_back();
                        number.pop_back();
                        number.push_back(cal(tmp[2], tmp[3], sym2));
                        number.push_front(tmp[0]);
                    }
                }
            }
            else if (sym1 == '*' || sym1 == '/') {
                if (sym2 == '+' || sym2 == '-') {
                    symbol.pop_front();
                    number.pop_front();
                    number.push_front(cal(tmp[0], tmp[1], sym1));
                    number.push_back(tmp[3]);
                }
                else {
                    ll num1 = cal(tmp[0], tmp[1], sym1);
                    ll num2 = cal(tmp[2], tmp[3], sym2);
 
                    if (num1 >= num2) {
                        symbol.pop_front();
                        number.pop_front();
                        number.push_front(cal(tmp[0], tmp[1], sym1));
                        number.push_back(tmp[3]);
                    }
                    else {
                        symbol.pop_back();
                        number.pop_back();
                        number.push_back(cal(tmp[2], tmp[3], sym2));
                        number.push_front(tmp[0]);
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
반응형

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

 

13544번: 수열과 쿼리 3

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/462

 

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)

1. 머지 소트 트리(Merge Sort Tree) 머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다. 2. 머지 소트 트리(Merge Sort Tree) 동작 원리 머지 소트 트리(Me

rudalsd.tistory.com

 

1. 수열을 입력받고, 머지 소트 트리를 구현합니다.

 

2. a, b, c를 입력받고 pre에 xor 한 후 그 값을 이용하여 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. ans를 출력하고, pre에 ans를 저장한 후 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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
int pre;
 
void merge(int node, int s, int e)
{
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0, j = 0;
 
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i < s_size) {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
    else {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
 
void getTree(int node, int s, int e, int i, int j, int k)
{
    if (s > j || e < i) return;
    if (i <= s && e <= j) {
        ans += mergeSortTree[node].end() - upper_bound(mergeSortTree[node].begin(), mergeSortTree[node].end(), k);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, i, j, k);
    getTree(node * 2 + 1, m + 1, e, i, j, k);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    cin >> M;
 
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
 
        ans = 0;
 
        a ^= pre;
        b ^= pre;
        c ^= pre;
 
        getTree(1, 1, N, a, b, c);
 
        cout << ans << '\n';
 
        pre = ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
반응형

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

 

21276번: 계보 복원가 호석

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 조상으로부터 자손으로 이어지는 단방향 그래프를 list 배열에 저장합니다.

 

2. 1과 동시에 조상의 개수를 cnt[ i ]++를 통해 저장해 주고, cnt[ i ]가 0이면 queue에 넣어줍니다.

 

3. queue를 돌면서 cnt[ i ]가 0일 때 queue에 해당 자손을 넣어주고, 그때의 조상이 직계 조상이므로 child 배열에 해당 자손을 넣어줍니다.

 

4. 가장 초기에 cnt[ i ]가 0인 조상은 가문의 시조이므로 parent 배열에 넣어줍니다.

 

5. 조건에 맞게 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
 
using namespace std;
 
int N, M;
map<string, int> m;
string str[1000];
int cnt[1000];
map<string, vector<string>> child;
vector<int> list[1000];
vector<string> parent;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> str[i];
        m[str[i]] = i;
    }
 
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        string tmp[2];
        cin >> tmp[0] >> tmp[1];
        cnt[m[tmp[0]]]++;
        list[m[tmp[1]]].push_back(m[tmp[0]]);
    }
 
    queue<int> q;
 
    for (int i = 0; i < N; i++) {
        if (cnt[i] == 0) {
            q.push(i);
            parent.push_back(str[i]);
        }
    }
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            cnt[next]--;
            if (cnt[next] == 0) {
                child[str[cur]].push_back(str[next]);
                q.push(next);
            }
        }
    }
 
    sort(parent.begin(), parent.end());
 
    cout << parent.size() << '\n';
 
    for (auto& next : parent) {
        cout << next << ' ';
    }
 
    cout << '\n';
 
    sort(str, str + N);
 
    for (int i = 0; i < N; i++) {
        cout << str[i] << ' ' << child[str[i]].size() << ' ';
        sort(child[str[i]].begin(), child[str[i]].end());
        for (auto& next : child[str[i]]) {
            cout << next << ' ';
        }
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
반응형

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

 

3780번: 네트워크 연결

입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언하고, vect[ i ] = i로 초기화합니다.

 

2. I 커맨드를 입력 받을 때마다 I와 J를 연결해 주고, dist[ I ] = abs(I - J) % 1000으로 갱신해 줍니다.

 

3. E 커맨드를 입력받을 때마다 Find 함수를 통해 부모 노드를 찾아주고, 각 노드에서 부모 노드까지의 거리를 dist[ num ] 에 저장해 줍니다.

 

4. dist[ 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
53
54
55
56
57
58
59
60
#include<iostream>
 
using namespace std;
 
int T, N;
int vect[20001];
int dist[20001];
 
pair<int,int> Find(int num)
{
    if (vect[num] == num) return make_pair(num, dist[num]);
    pair<int,int> temp = Find(vect[num]);
    vect[num] = temp.first;
    dist[num] += temp.second;
    return make_pair(vect[num], dist[num]);
}
 
void Union(int I, int J)
{
    vect[I] = J;
    dist[I] = abs(J - I) % 1000;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
            dist[i] = 0;
        }
 
        while (1) {
            char cmd;
            cin >> cmd;
 
            if (cmd == 'E') {
                int I;
                cin >> I;
                Find(I);
 
                cout << dist[I] << '\n';
            }
            else if (cmd == 'I') {
                int I, J;
                cin >> I >> J;
 
                Union(I, J);
            }
            else break;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
[ 백준 ] 17299번 - 오등큰수 (C++)  (1) 2023.10.06
반응형

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

 

17299번: 오등큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, cnt[ arr[ i ] ]의 값이 s.top보다 클 경우 s.pop을 해주고, s가 완전히 비기 전까지 반복해 줍니다.

 

2. NGF 배열을 만들고, 1의 s.pop 과정에서 NGF 배열의 해당 숫자의 idx  값을 arr[ i ]로 갱신합니다. 

 

3. s에 cnt[ arr[ i ] ]를 push 합니다.

 

4. NGF 배열을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
int arr[1000000];
int cnt[1000001];
int NGF[1000000];
stack<pair<int, int>> s;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    fill(NGF, NGF + N, -1);
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        cnt[arr[i]]++;
    }
 
    for (int i = 0; i < N; i++) {
        if (!s.empty()) {
            while (s.top().first < cnt[arr[i]]) {
                NGF[s.top().second] = arr[i];
                s.pop();
                if (s.empty()) break;
            }
        }
 
        s.push({ cnt[arr[i]], i });
    }
 
    for (int i = 0; i < N; i++) {
        cout << NGF[i] << ' ';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04
[ 백준 ] 1461번 - 도서관 (C++)  (0) 2023.10.03
반응형

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

 

1354번: 무한 수열 2

첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map< ll, ll> um을 선언합니다.

 

2. 재귀함수를 통해 n이 0보다 작거나 같으면 1을 return하고, um.count(n)이 0일 때 um[ n ] = dfs(n / P) + dfs(n / Q)를 통해 um[ n ]을 구해줍니다.

 

3. dfs(N)을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
ll N;
int P, Q, X, Y;
unordered_map<ll, ll> um;
 
ll dfs(ll n)
{
    if (n <= 0) return um[n] = 1;
    if (um.count(n) != 0) return um[n];
 
    return um[n] = dfs(n / P - X) + dfs(n / Q - Y);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> P >> Q >> X >> Y;
 
    cout << dfs(N);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04
[ 백준 ] 1461번 - 도서관 (C++)  (0) 2023.10.03
[ 백준 ] 2174번 - 로봇 시뮬레이션 (C++)  (0) 2023.10.01
[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
[ 백준 ] 9177번 - 단어 섞기 (C++)  (0) 2023.09.29
반응형

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

 

1351번: 무한 수열

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map< ll, ll> um을 선언하고, um[ 0 ] = 1로 초기화합니다.

 

2. 재귀함수를 통해 um.count(n)이 0일 때 um[ n ] = dfs(n / P) + dfs(n / Q)를 통해 um[ n ]을 구해줍니다.

 

3. dfs(N)을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
ll N;
int P, Q;
unordered_map<ll, ll> um;
 
ll dfs(ll n)
{
    if (um.count(n)) return um[n];
 
    return um[n] = dfs(n / P) + dfs(n / Q);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> P >> Q;
 
    um[0] = 1;
 
    cout << dfs(N);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
[ 백준 ] 9177번 - 단어 섞기 (C++)  (0) 2023.09.29
[ 백준 ] 14925번 - 목장 건설하기 (C++)  (0) 2023.09.27
[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)  (0) 2023.09.26
[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
반응형

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

 

3197번: 백조의 호수

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 현재 호수의 상태를 저장할 queue<pair<int, int>> water, 다음 호수의 상태를 저장할 queue<pair<int, int>> tmpW, 현재 백조의 위치를 저장할 queue<pair<int, int>> swan, 마지막으로 다음 백조의 위치를 저장할 queue<pair<int, int>> tmpS를 선언합니다.

 

2. 호수를 입력받으면서 얼음이 아닌 좌표를 water에 push 하고, 백조 한 마리의 위치를 swan에 push 합니다.

 

3. 먼저 백조가 만날 수 있는지 bfs를 통해 움직이고, 벽에 마주칠 때마다 다음에 갈 수 있는 위치이므로 tmpS에 push 하고, 백조를 만난다면 Find 변수를 true로 갱신합니다.

 

4. 빙하가 녹으면서 현재 물에 맞닿아 있다면 tmpW에 push 해줍니다.

 

5. Find 변수가 true라면 ans를 출력해 주고, 그렇지 않다면 water = tmpW, swan = tmpS로 갱신해 주고, 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<queue>
 
using namespace std;
 
int R, C;
int r, c;
char arr[1500][1501];
int visited[1500][1500];
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
queue<pair<int, int>> swan, water, tmpW, tmpS;
bool Find = false;
 
void BFSwater()
{
    while (!water.empty()) {
        const int r = water.front().first;
        const int c = water.front().second;
        water.pop();
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr >= 0 && rr < R && cc >= 0 && cc < C) {
                if (arr[rr][cc] == 'X') {
                    tmpW.push({ rr,cc });
                    arr[rr][cc] = '.';
                }
            }
        }
    }
}
 
void BFSswan()
{
    while (!swan.empty() && Find == false) {
        const int r = swan.front().first;
        const int c = swan.front().second;
        swan.pop();
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr >= 0 && rr < R && cc >= 0 && cc < C && visited[rr][cc] == 0) {
                visited[rr][cc] = 1;
                if (arr[rr][cc] == '.') {
                    swan.push({ rr,cc });
                }
                else if (arr[rr][cc] == 'X') {
                    tmpS.push({ rr,cc });
                    arr[rr][cc] = '.';
                }
                else if (arr[rr][cc] == 'L') {
                    Find = true;
                    break;
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
        for (int j = 0; j < C; j++) {
            if (arr[i][j] != 'X') {
                water.push({ i,j });
            }
            if (arr[i][j] == 'L') {
                r = i;
                c = j;
            }
        }
    }
 
    swan.push({ r,c });
    visited[r][c] = 1;
 
    int ans = 0;
 
    while (1) {
        BFSswan();
        if (Find == true) {
            cout << ans;
            return 0;
        }
        BFSwater();
        ans++;
 
        water = tmpW;
        swan = tmpS;
 
        tmpW = queue<pair<int, int>>();
        tmpS = queue<pair<int, int>>();
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)  (0) 2023.09.26
[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
반응형

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/12016

 

12016번: 라운드 로빈 스케줄러

첫째 줄에 작업의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 각 작업을 수행해야하는 시간이 공백으로 구분되어 주어진다. 각 작업을 수행해야하는 시간은 1보다 크거나 같고, 1,000,000,000보다

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. 작업의 각 번호의 값을 1로 대입해 Segment Tree를 채웁니다.

 

2. 작업 수행 시간을 입력받고, 작업 수행 시간을 기준으로 오름차순으로, 작업의 번호를 기준으로 내림차순으로 정렬합니다.

 

3. 현재까지 작업한 작업의 개수를 Cur에 저장하고, 현재 같은 작업수를 가진 작업들의 수를 cnt, 현재 같은 작업수를 가진 작업들과 이전의 같은 작업수를 가진 작업들과의 차를 cur에 저장하고, 현재 남아있는 작업의 개수를 Cnt에 저장합니다.

 

4. 이전 작업의 수행 시간과 현재 작업의 수행 시간이 같다면 cnt++를 수행하고, 해당 작업 번호의 segment tree 노드의 값을 -1 해주고, ans[ arr[ i ].second ] = Cur + getTree(N, N + arr[ i ].second - 1) + cur * Cnt 의 식을 이용하여 ans배열을 채웁니다.

 

5. 이전 작업의 수행 시간과 현재 작업의 수행 시간이 다르다면

Cur += Cnt * (cur + 1);
Cnt -= cnt;
cnt = 0;
cur = arr[ i ].first - arr[ i - 1 ].first - 1;
temp = arr[ i ].first;
i--;

를 수행해줍니다.

 

6. 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
86
87
88
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int N;
int segTree[200000];
pair<int, int> arr[100001];
ll ans[100001];
 
bool cmp(pair<int, int> left, pair<int, int> right)
{
    if (left.first == right.first) return left.second > right.second;
    return left.first < right.first;
}
 
void updateTree(int idx, int diff)
{
    while (idx) {
        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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        updateTree(N + i - 1, 1);
        cin >> arr[i].first;
        arr[i].second = i;
    }
 
    sort(arr + 1, arr + N + 1, cmp);
 
    int temp = arr[1].first;
    int cnt = 0;
    int Cnt = N;
    int cur = arr[1].first - 1;
    ll Cur = 0;
 
    for (int i = 1; i <= N; i++) {
        if (temp == arr[i].first) {
            cnt++;
            ans[arr[i].second] = Cur + (ll)getTree(N, N + arr[i].second - 1) + 1LL * cur * Cnt;
            updateTree(N + arr[i].second - 1, -1);
        }
        else {
            Cur += 1LL * Cnt * (1LL * cur + 1);
            Cnt -= cnt;
            cnt = 0;
            cur = arr[i].first - arr[i - 1].first - 1;
            temp = arr[i].first;
            i--;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17

+ Recent posts

티스토리툴바