반응형

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

 

1477번: 휴게소 세우기

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 휴게소의 위치를 1부터 N까지 입력받고, 배열을 오름차순으로 정렬합니다. 이때, 0번 인덱스의 값은 0, N+1번 인덱스의 값은 L로 설정합니다.

 

2. 공유기의 간격이 최소 1에서 최대 999이므로 left = 1, right = 1,000으로 설정하고, 이분 탐색을 진행해 줍니다. 

 

3. mid = (left + right) / 2로 설정하고, 0번 째 인덱스를 기준으로 해당 mid 값보다 더 떨어져 있는 휴게소가 없다면 cnt++를 해주고, 다음 휴게소가 나올 때까지 mid를 더해줍니다. 다음 휴게소가 나오면 기준을 해당 휴게소로 바꿔줍니다. 이를 반복하며 cnt가 M보다 크다면 left = mid + 1이 되고, 그렇지 않다면 right = mid가 됩니다. 

 

4. mid 값 중 가장 작은 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int N, M, L;
int arr[152];
 
bool check(int mid)
{
    int base = arr[0];
    int cnt = 0;
 
    for (int i = 0; i <= N; i++) {
        while (1) {
            base += mid;
            if (base >= arr[i + 1]) break;
            cnt++;
        }
 
        if (cnt > M) return false;
        base = arr[i + 1];
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> L;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    arr[0] = 0;
    arr[N + 1] = L;
 
    sort(arr, arr + N + 2);
 
    int left = 1;
    int right = 1000;
    int ans = 987654321;
 
    while (left < right) {
        int mid = (left + right) / 2;
 
        if (check(mid)) {
            ans = min(ans, mid);
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15
[ 백준 ] 2295번 - 세 수의 합 (C++)  (0) 2023.07.14
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
[ 백준 ] 3151번 - 합이 0 (C++)  (0) 2023.07.10
반응형

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 공유기의 위치를 입력받고, 배열을 오름차순으로 정렬합니다.

 

2. 공유기의 간격이 최소 0에서 최대 1,000,000,000이므로 left = 0, right = 1,000,000,001로 설정하고, 이분 탐색을 진행해줍니다. 

 

3. mid = (left + right) / 2로 설정하고, 0번 째 공유기를 기준으로 해당 mid 값보다 더 떨어져 있는 공유기가 있다면 cnt++를 해주고, 기준을 해당 공유기로 바꿔줍니다. 이를 반복하며 cnt가 C보다 크거나 같다면 left = mid + 1이 되고, 그렇지 않다면 right = mid가 됩니다. 

 

4. mid 값 중 가장 큰 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int N, C;
int arr[200000];
 
bool check(int mid)
{
    int base = arr[0];
    int cnt = 1;
 
    for (int i = 1; i < N; i++) {
        if (arr[i] - base >= mid) {
            base = arr[i];
            cnt++;
        }
 
        if (cnt >= C) return true;
    }
 
    return false;
}
 
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];
    }
 
    sort(arr, arr + N);
 
    int left = 0;
    int right = 1000000001;
    int ans = 0;
 
    while (left < right) {
        int mid = (left + right) / 2;
 
        if (check(mid)) {
            left = mid + 1;
            ans = max(ans, mid);
        }
        else {
            right = mid;
        }
    }
 
    cout << ans;
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2295번 - 세 수의 합 (C++)  (0) 2023.07.14
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
[ 백준 ] 3151번 - 합이 0 (C++)  (0) 2023.07.10
[ 백준 ] 5430번 - AC (C++)  (0) 2023.07.09
반응형

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

 

1800번: 인터넷 설치

첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ N ][ K ] 배열을 만들어 인터넷을 K번 공짜로 연결했을 때 해당 노드까지의 연결 값 중 최댓값을 저장합니다.

 

2. dijkstra를 통해 공짜로 연결했을 때와 하지 않았을 때 각각 priority_queue에 넣어줍니다.

 

3. N번 도시에 도착했을 때 dist를 출력합니다.

 

[ 소스코드 ]

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>
#include<queue>
#include<vector>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int cnt;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
int N, P, K;
vector<pair<int, int>> list[1001];
int visited[1001][1001];
 
int main()
{
    scanf("%d %d %d", &N, &P, &K);
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = 1111111111;
        }
    }
 
    for (int i = 0; i < P; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> temp;
 
    pq.push({ 1,0,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const int cost = pq.top().cost;
        const int cnt = pq.top().cnt;
        pq.pop();
 
        if (visited[cur][cnt] < cost) continue;
        visited[cur][cnt] = cost;
 
        if (cur == N) {
            printf("%d", cost);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            const int nNode = next.first;
            const int nCost = next.second;
 
            if (cnt < K) {
                if (visited[nNode][cnt + 1] > cost) {
                    pq.push({ nNode,cost,cnt+1 });
                }
            }
 
            if (visited[nNode][cnt] > max(cost, nCost)) {
                pq.push({ nNode,max(cost,nCost),cnt });
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11

+ Recent posts

티스토리툴바