반응형

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

 

20917번: 사회적 거리 두기

Albert는 L대학에서 주최하는 Hackathon 행사 진행을 도와주기로 했는데, 사회적 거리 두기 방침에 따라 모든 참가자들을 최대한 멀리 떨어트려 좌석 배정을 해주려 한다. 이를 위해 아주 길다란 복

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. n과 s를 입력받고, vector<int> arr에 콘센트 좌표를 저장합니다.

 

2. arr를 오름차순으로 정렬하고, a = 0, b = 1,000,000,000으로 저장한 후 매개변수 탐색을 실시합니다.

 

3. m = (a + b) / 2를 통해 m을 갱신하고, tmp = arr[ 0 ], cnt = 1로 시작하여 이분 탐색을 이용해 다음 콘센트의 위치를 찾습니다. < lower_bound(arr.begin(), arr.end(), tmp + m) >

 

4. 다음 콘센트의 위치가 범위를 벗어나지 않으면 cnt++를 해주고, cnt의 값이 s보다 크거나 같으면 true를 반환하고, 그렇지 않다면 false를 반환합니다.

 

5. true를 반환받으면 ans = m 후 a = m + 1로 갱신해 주고, false를 반환받으면 b = m으로 갱신해 주고 매개변수탐색을 계속 진행합니다.

 

6. a < b일 때까지 계속 반복해 준 후 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int T;
int n, s;
vector<int> arr;
 
bool check(int m)
{
    int tmp = arr[0];
    int cnt = 1;
    while (1) {
        auto it = lower_bound(arr.begin(), arr.end(), tmp + m);
        if (it == arr.end()) break;
        tmp = *it;
        cnt++;
    }
 
    if (cnt >= s) return true;
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> n >> s;
 
        arr.clear();
 
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            arr.push_back(num);
        }
 
        sort(arr.begin(), arr.end());
 
        int a, b;
        a = 0;
        b = 1000000000;
        int ans = 0;
 
        while (a < b) {
            int m = (a + b) / 2;
 
            if (check(m)) {
                ans = m;
                a = m + 1;
            }
            else {
                b = m;
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11311번 - Jug Hard (C++)  (0) 2023.10.26
[ 백준 ] 14881번 - 물통 문제 (C++)  (0) 2023.10.25
[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
반응형

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

 

20183번: 골목 대장 호석 - 효율성 2

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, vector<pair<int, int>> list[ 100001 ] 배열에 저장합니다. 

 

2. 매개 변수를 활용하여 이동할 수 있는 골목의 최대 비용을 정해서 dijkstra를 돌립니다.

 

3. ans를 -1로 초기화하고, 만약 도착지에 도착하게 되면 ans에 해당 매개 변수 값을 저장합니다.

 

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
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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
int N, M;
int A, B;
ll C;
vector<pair<int, int>> list[100001];
int s, e;
int ans = -1;
ll visited[100001];
 
bool dijkstra(int m)
{
    fill(visited, visited + N + 1, 111111111111111);
    priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
 
    pq.push({ 0,A });
 
    while (!pq.empty()) {
        const ll cost = pq.top().first;
        const int cur = pq.top().second;
        pq.pop();
 
        if (cost > C) continue;
 
        if (cur == B) {
            return true;
        }
 
        if (visited[cur] < cost) continue;
        visited[cur] = cost;
 
        for (auto& next : list[cur]) {
            if (visited[next.second] > cost + next.first && next.first <= m) {
                visited[next.second] = cost + next.first;
                pq.push({ cost + next.first, next.second });
            }
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> A >> B >> C;
    s = 1;
 
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        list[u].push_back({ w,v });
        list[v].push_back({ w,u });
        e = max(e, w);
    }
 
    while (s <= e) {
        int m = (s + e) / 2;
 
        if (dijkstra(m)) {
            ans = m;
            e = m - 1;
        }
        else {
            s = m + 1;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
반응형

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

 

1939번: 중량제한

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. arr 배열을 거리를 기준으로 내림차순으로 정렬합니다.

 

3. Union-Find를 이용하여 각 지점들을 연결하고, 각 공장 사이에 길이 완성되었다면 연결된 순간의 다리의 길이를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, C;
};
 
bool cmp(node left, node right)
{
    return left.C > right.C;
}
 
int N, M;
node arr[100000];
int vect[10001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int A, int B)
{
    int pA = Find(A);
    int pB = Find(B);
 
    vect[pB] = pA;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        arr[i] = { A,B,C };
    }
 
    int s, e;
    cin >> s >> e;
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int C = arr[i].C;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
        }
 
        if (Find(s) == Find(e)) {
            cout << C;
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
반응형

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

 

16472번: 고냥이

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N과 문자열을 입력받고, 문자의 개수를 저장할 cnt 배열과 총 문자 종류의 개수를 저장할 ch배열을 초기화합니다.

 

2. s = 0, e = 0으로 초기화한 후 e < str.size()인 동안 반복하면서 총 문자 종류의 개수가 N개보다 적거나 같으면 ans에 문자열의 길이의 최댓값을 저장하고, e++, cnt++, 처음 나오는 문자라면 ch++를 해주고, N개보다 많다면 cnt--, s++, 해당 문자의 개수가 0개라면 ch--를 해줍니다.

 

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
#include<iostream>
#include<string>
 
using namespace std;
 
int N;
string str;
int cnt[26];
int ch;
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    cin >> str;
 
    int s = 0;
    int e = 0;
 
    cnt[str[0] - 'a']++;
    ch++;
    ans = 1;
 
    while (e < str.size()) {
        if (ch <= N) {
            ans = max(ans, e - s + 1);
            e++;
            if (cnt[str[e] - 'a'] == 0) ch++;
            cnt[str[e] - 'a']++;
        }
        else {
            cnt[str[s] - 'a']--;
            if (cnt[str[s] - 'a'] == 0) ch--;
            s++;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14
[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
반응형

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

 

3079번: 입국심사

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 심사대의 걸리는 시간을 arr 배열에 저장하고, 그 값 중 가장 작은 값을 저장합니다.

 

2. s = 0, e = Min * M + 1로 설정한 후 이분 탐색을 통해 해당 시간 안에 모두 통과가 가능하다면 e = m을 적용하고, ans = e를 해주고, 통과가 불가능하다면 s = m + 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
#include<iostream>
#define ll long long
 
using namespace std;
int arr[100000];
int N, M;
 
bool check(ll mid)
{
    ll num = 0;
 
    for (int i = 0; i < N; i++) {
        num += mid / arr[i];
 
        if (num >= M) {
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    int Min = 1111111111;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        Min = min(Min, arr[i]);
    }
 
    ll s = 0;
    ll e = 1LL * Min * M + 1;
    ll ans = 0;
 
    while (s < e) {
        ll m = (s + e) / 2;
 
        if (check(m)) {
            e = m;
            ans = e;
        }
        else {
            s = m + 1;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
반응형

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

 

2465번: 줄 세우기

첫째 줄에는 전체 사람의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 여기서 모든 키들은 2×109이하이다. 그리고 마지막 줄에 수열

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 키를 입력받고, map 자료구조를 활용해 각 키의 개수를 저장합니다.

 

2. 입력받은 키를 오름차순으로 정렬해 vector에 저장합니다.

 

3. vector의 인덱스를 기준으로 segment tree를 만듭니다.

 

4. 키의 순서를 N번째부터 1번째까지 돌면서 현재 남아있는 키 중에서 해당 정수 + 1만큼의 값을 가지고 있는 수를 ans 배열에 추가합니다.

 

5. ans 배열을 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<set>
#include<unordered_map>
#include<vector>
 
using namespace std;
 
int N;
int segTree[262222];
unordered_map<int, int> m;
set<int> se;
vector<int> arr;
vector<int> ans;
int seq[100000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] += m[arr[s]];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void updateTree(int node, int s, int e, int idx)
{
    segTree[node]--;
    if (s == e) {
        ans.push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    if (segTree[node * 2] >= idx) {
        updateTree(node * 2, s, m, idx);
    }
    else {
        updateTree(node * 2 + 1, m + 1, e, idx - segTree[node * 2]);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        se.insert(n);
        m[n]++;
    }
    
    arr.push_back(-1);
 
    for (auto& next : se) {
        arr.push_back(next);
    }
 
    makeTree(1, 1, arr.size() - 1);
 
    for (int i = 0; i < N; i++) {
        cin >> seq[i];
    }
 
    for (int i = N - 1; i >= 0; i--) {
        updateTree(1, 1, arr.size() - 1, seq[i] + 1);
    }
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
반응형

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

 

23326번: 홍익 투어리스트

도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. set 자료구조를 활용하여 명소의 위치를 저장합니다. 

 

2. arr배열을 만들어 해당 좌표가 명소인지 아닌지 체크합니다.

 

3. 1번 명령이 주어지면 명소인지 아닌지 arr배열로 체크하고, 명소라면 arr[ i ]를 0으로 바꾸고, set에서 erase 합니다. 반대의 경우 arr[ i ]를 1로 바꾸고, set에 insert 합니다.

 

4. 2번 명령이 주어지면 x %= N 후 현재 좌표에 x를 더해주고, 이후 좌표가 N보다 크다면 N을 빼줍니다.

 

5. 3번 명령이 주어지면 set이 비어있다면 -1을 출력하고, 그렇지 않다면 현재 좌표를 기준으로 lower_bound를 해주고, 그 값에 현재 좌표를 뺀 값을 출력합니다.

 

6. 5번에서 lower_bound의 결과가 set.end()라면 N - cur + lower_bound(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
66
67
68
#include<iostream>
#include<set>
 
using namespace std;
 
int N, Q;
int cur = 1;
int arr[500001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
    set<int> s;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        if (arr[i] == 1) {
            s.insert(i);
        }
    }
 
    for (int i = 0; i < Q; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i;
            cin >> i;
            if (arr[i] == 0) {
                arr[i] = 1;
                s.insert(i);
            }
            else {
                arr[i] = 0;
                s.erase(i);
            }
        }
        else if (cmd == 2) {
            int x;
            cin >> x;
            if (x > N) {
                x %= N;
            }
            cur += x;
            if (cur > N) {
                cur -= N;
            }
 
        }
        else {
            if (s.empty()) {
                cout << -1 << '\n';;
            }
            else {
                if (s.lower_bound(cur) == s.end()) {
                    cout << N - cur + (*s.lower_bound(0)) << '\n';;
                }
                else {
                    cout << (*s.lower_bound(cur)) - cur << '\n';;
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
반응형

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

티스토리툴바