반응형

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

 

20210번: 파일 탐색기

첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다. 모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받고, arr 배열에 저장합니다.

 

2. cmp 함수를 만들어 문자열을 서로 비교하면서 두 문자열이 모두 숫자가 나온다면 0이 아닌 숫자가 나온 시점부터 string에 넣어줍니다.

 

3. 두 숫자가 같을 때 사이즈가 다르면 사이즈가 더 작은 수를 앞에 두고, 사이즈가 같다면 각 자리 숫자를 비교해 주면서 더 작은 숫자를 앞에 둡니다.

 

4. cmp함수를 통해 arr 배열을 정렬해주고, arr배열을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
#include<algorithm>
 
using namespace std;
 
int N;
string arr[10000];
 
bool cmp(string left, string right)
{
    if (left == right) return false;
 
    int l = 0, r = 0;
    while (1) {
        if (l == left.size()) {
            return true;
        }
        if (r == right.size()) {
            return false;
        }
 
        if (left[l] <= '9' && right[r] <= '9') {
            int sizeL = 0, sizeR = 0;
            string L, R;
            bool zeroL = false, zeroR = false;
            while (left[l] <= '9' && l < left.size()) {
                if (left[l] != '0' && zeroL == false) {
                    zeroL = true;
                }
                
                if (zeroL) {
                    L += left[l];
                }
 
                l++;
                sizeL++;
            }
 
            while (right[r] <= '9' && r < right.size()) {
                if (right[r] != '0' && zeroR == false) {
                    zeroR = true;
                }
 
                if (zeroR) {
                    R += right[r];
                }
                r++;
                sizeR++;
            }
 
            if (R == L) {
                if (sizeL != sizeR) {
                    return sizeL < sizeR;
                }
            }
            else {
                if (L.size() == R.size()) {
                    for (int i = 0; i < L.size(); i++) {
                        if (L[i] != R[i]) {
                            return L[i] < R[i];
                        }
                    }
                }
                return L.size() < R.size();
            }
            continue;
        }
        
        if (left[l] != right[r]) {
            if (left[l] >= 'a') {
                if (right[r] >= 'a') {
                    return left[l] < right[r];
                }
                else if (right[r] >= 'A') {
                    return left[l] - 'a' < right[r] - 'A';
                }
                else {
                    return false;
                }
            }
            else if (left[l] >= 'A') {
                if (right[r] >= 'a') {
                    return left[l] - 'A' <= right[r] - 'a';
                }
                else if (right[r] >= 'A') {
                    return left[l] < right[r];
                }
                else {
                    return false;
                }
            }
            else {
                if (right[r] >= 'A') {
                    return true;
                }
            }
        }
 
        l++;
        r++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + N, cmp);
 
    for (int i = 0; i < N; i++) {
        cout << arr[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
[ 백준 ] 17299번 - 오등큰수 (C++)  (1) 2023.10.06
[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
반응형

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

 

1461번: 도서관

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vector<int> L, R을 선언하고, 좌표가 음수라면 L에 push, 좌표가 양수라면 R에 push합니다.

 

2. L은 내림차순으로 정렬하고, R은 오름차순으로 정렬합니다.

 

3. L과 R의 끝 좌표부터 책을 옮기고 책의 원래 좌표 * 2 를 ans에 더해줍니다.

 

4. L과 R의 끝 좌표중 더 큰 값을 ans에서 빼주고, 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N, M;
vector<int> L, R;
int ans;
int Max;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        if (n < 0) {
            L.push_back(n);
        }
        else {
            R.push_back(n);
        }
    }
 
    sort(R.begin(), R.end());
    sort(L.begin(), L.end(), greater<>());
 
    for (int i = R.size() - 1; i >= 0; i -= M) {
        ans += R[i] * 2;
    }
 
    for (int i = L.size() - 1; i >= 0; i -= M) {
        ans += -L[i] * 2;
    }
 
    if (!R.empty()) Max = max(Max, *R.rbegin());
    if (!L.empty()) Max = max(Max, -(*L.rbegin()));
 
    cout << ans - Max;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04
[ 백준 ] 1354번 - 무한 수열 2 (C++)  (0) 2023.10.02
[ 백준 ] 2174번 - 로봇 시뮬레이션 (C++)  (0) 2023.10.01
[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
반응형

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
반응형

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

 

16936번: 나3곱2

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 입력받고, arr에 저장합니다.

 

2. 재귀함수를 이용하여 수열을 채워 나가는데, 이전 값에 2를 곱한 값이나 3을 나눈 값이 현재 수열의 값일 때만 수열에 넣어줍니다.

 

3. 모든 자리가 다 찬다면 그대로 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll arr[100];
ll ans[100];
int visited[100];
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
 
    if (level == N) {
        for (int i = 0; i < N; i++) {
            cout << ans[i] << ' ';
        }
 
        flag = true;
    }
 
    for (int i = 0; i < N; i++) {
        if (visited[i] == 0 && (ans[level-1] * 2 == arr[i] || (ans[level-1] % 3 == 0 && ans[level - 1] / 3 == arr[i]))) {
            visited[i] = 1;
            ans[level] = arr[i];
            dfs(level + 1);
            visited[i] = 0;
            ans[level] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        visited[i] = 1;
        ans[0] = arr[i];
        dfs(1);
        ans[0] = 0;
        visited[i] = 0;
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
반응형

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

 

9024번: 두 수의 합

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 입력받고, 두 정수의 합과 K의 차의 절댓값의 최댓값은 $3 \times 10^{8}$ 이므로 min을 322,222,222로 초기화해 줍니다.

 

2. s = 0, e = n - 1로 초기화한 후 s < e인 동안 반복하면서 두 정수의 합과 K의 차의 절댓값이 min보다 작으면 ans = 1로 초기화하고, 절댓값이 min과 같다면 ans++를 해줍니다.

 

3. 이후 K가 두 정수의 합보다 크다면 s++, 아니라면 e--를 해줍니다.

 

4. 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
#include<iostream>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
int t, n, K;
int arr[1000000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    for (int T = 0; T < t; T++) {
        cin >> n >> K;
 
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
 
        sort(arr, arr + n);
 
        int s = 0;
        int e = n - 1;
        int ans = 0;
        int min = 322222222;
 
        while (s < e) {
            int temp = arr[s] + arr[e];
 
            if (abs(temp - K) < min) {
                ans = 1;
                min = abs(temp - K);
            }
            else if (abs(temp - K) == min) {
                ans++;
            }
 
            if (K > temp)s++;
            else e--;
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
반응형

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

 

18114번: 블랙 프라이데이

첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 물건의 무게를 입력받고, 그 중 C와 값이 같은 물건이 있으면 1을 출력하고 프로그램을 종료합니다.

 

2. 1에서 무게가 C와 같은 물건이 없었다면 투포인터를 이용하여 물건 두 개를 골라 무게가 C와 같은 조합이 있으면 1을 출력하고 프로그램을 종료합니다.

 

3. 1, 2에서 무게가 C와 같은 조합이 없다면 0부터 N-3까지 for문을 이용해 돌면서 투포인터를 활용하여 물건 세 개를 골라 무게가 C와 같은 조합이 있으면 1을 출력하고 프로그램을 종료합니다.

 

4. 1, 2, 3에서 무게가 C와 같은 조합이 없다면 0을 출력합니다.

 

[ 소스코드 ]

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>
#include<algorithm>
 
using namespace std;
 
int N, C;
int arr[5000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (arr[i] == C) {
            cout << 1;
            return 0;
        }
    }
 
    sort(arr, arr + N);
 
    int s = 0;
    int e = N - 1;
 
    while (s < e) {
        int temp = arr[s] + arr[e];
 
        if (temp > C) {
            e--;
        }
        else if (temp < C) {
            s++;
        }
        else {
            cout << 1;
            return 0;
        }
    }
 
    for (int i = 0; i < N - 2; i++) {
        s = i + 1;
        e = N - 1;
 
        while (s < e) {
            int temp = arr[i] + arr[s] + arr[e];
 
            if (temp > C) {
                e--;
            }
            else if (temp < C) {
                s++;
            }
            else {
                cout << 1;
                return 0;
            }
        }
    }
 
    cout << 0;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
반응형

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

 

13537번: 수열과 쿼리 1

길이가 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. 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

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
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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
 
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;
    int 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 (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
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 (e < i || j < s) 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;
 
    for (int a = 0; a < M; a++) {
        int i, j, k;
        cin >> i >> j >> k;
        ans = 0;
 
        getTree(1, 1, N, i, j, k);
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
반응형

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

 

7453번: 합이 0인 네 정수

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수들을 입력받아 arr 배열에 저장하고, arr 배열에서 두 수를 뽑아 더한 값을 sum 배열에 저장합니다. 

 

2. sum 배열을 오름차순으로 정렬합니다.

 

3. 이중 for문을 이용하여 i = N - 1부터 0까지, j는 0부터 N까지 탐색하면서 arr[ i ] + arr[ j ]가 sum 배열에 존재하는지 lower_bound를 활용하여 찾아줍니다.

 

4. sum 배열에 존재한다면 upper_bound를 활용하여 같은 수가 있다면 그 개수만큼 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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int arr[4][4000];
vector<int> sum;
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> arr[j][i];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum.push_back(arr[0][i] + arr[1][j]);
        }
    }
 
    sort(sum.begin(), sum.end());
 
    ll ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp = arr[2][i] + arr[3][j];
 
            auto it = lower_bound(sum.begin(), sum.end(), -temp);
 
            if (*it == -temp) {
                ans += upper_bound(sum.begin(), sum.end(), -temp) - it;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 2295번 - 세 수의 합 (C++)  (0) 2023.07.14
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12

+ Recent posts

티스토리툴바