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

 

회의는 한번에 하나만 진행이 가능하며, 주어지는 N개의 회의들을 적절하게 배정하여 최대 인원을 구하는 문제입니다.

저는 dp + parametric search로 접근했습니다.

dp[N]: N번째 회의부터 모을 수 있는 최대 인원

 

우선 회의들을 시작시간 기준 오름차순으로 정렬합니다.

그리고 해당 회의를 진행하거나, 진행하지 않거나 두가지를 모두 확인할 수 있습니다.

 

이번 회의를 넘긴다면 바로 idx + 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
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 100001
using namespace std;
 
typedef struct Node {
    int l, r, s;
}Node;
 
Node list[MAX];
int dp[MAX];
int N;
 
bool cmp(Node a, Node b) {
    return a.l < b.l;
}
 
int bs(int x) {
    int l = 0;
    int r = N;
    while (l < r) {
        int m = (l + r) >> 1;
        if (list[m].l >= x) r = m;
        else l = m + 1;
    }
    return l;
}
 
int solve(int idx) {
    if (idx >= N) return 0;
 
    int& ret = dp[idx];
    if (ret != -1) return ret;
 
    return ret = max(solve(idx + 1), list[idx].s + solve(bs(list[idx].r)));
}
 
void func() {
    sort(list, list + N, cmp);
    memset(dp, -1, sizeof(dp));
    cout << solve(0) << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].l >> list[i].r >> list[i].s;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 30461 낚시  (0) 2024.07.28
boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29

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

 

27977번: 킥보드로 등교하기

첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개

www.acmicpc.net

지인분이 출제한 대회문제가 백준에 등록되었습니다.

문제출제라니.. 무슨 문제를 만들어야하고, 테케는 어떻게 만드는지 모르는 입장에서 그저 신기하네요 ㅋㅋㅋ

다행히 제가 풀수있는 문제를 만들어 주셨습니다 ㅎㅎ

 

이 문제는 0에서 출발하여 L까지 정해진 배터리 용량으로 목적지까지 가야합니다.

충전소는 N개, A[i] 지점마다 있으며, 최대 K번 충전이 가능합니다.

이 때 최초 구매할 수 있는 배터리 용량의 최소를 구하는 문제입니다.

 

최종으로 구해야 하는건 배터리 용량의 최소이므로 이를 파라매트릭 서치로 구해야 합니다.

목적지까지는 갈 수 있어야하므로 최소 용량 l은 maxDis가 되겠고, 최대 용량 r은 출발지점에서 목적지까지의 거리 L이 되겠습니다.

maxDis는 출발지점과 첫 번째 충전소, 각 인접한 충전소들, 마지막 충전소와 도착지점 사이의 거리의 최대입니다.

그리고 계산의 편의를 위해 배열에 도착지점인 L을 추가합니다.

이 문제는 충전소의 위치가 정렬된 상태로 주어지므로 정렬로직이 필요 없습니다.

 

그러면 배터리 용량이 m이라고 했을 때, 충전소를 K번 이하 방문하면서 목적지점인 L 까지 갈 수 있는지 확인합니다.

L에 도착했을 때 충전소를 K번 이하로 방문할 수 있다면 ret을 갱신하고 범위를 작게 맞춰서 최적 해를 구합니다.

 

 

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>
#define MAX_N 100001
using namespace std;
 
int list[MAX_N];
int L, N, K, maxDis;
 
void func() {
    int l = maxDis;
    int r = L;
 
    int ret = 0;
    while (l <= r) {
        int m = (l + r) / 2;
 
        int now = m;
        int pos = 0;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] - pos > now) {
                cnt++;
                now = m;
            }
            now -= (list[i] - pos);
            pos = list[i];
        }
 
        if (cnt <= K) {
            ret = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> L >> N >> K;
 
    int pre = 0;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        maxDis = max(maxDis, list[i] - pre);
        pre = list[i];
    }
    maxDis = max(maxDis, L - pre);
    list[N++] = L;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

'algorithm > binarysearch' 카테고리의 다른 글

boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22

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

 

18113번: 그르다 김가놈

첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다.

www.acmicpc.net

김밥의 꼬다리를 K * 2 만큼 잘라낸 김밥을 손질된 김밥이라고 하며, K * 2보다 작은 김밥은 K만큼만 잘라낸다고 합니다.

그 손질된 김밥을 길이가 P인 조각으로 잘라내 최소 M개의 조각을 만드려고 합니다.

-> 최소 M개의 조각을 만들기 위한 최대 P를 구하는 문제로 파라매트릭 서치를 이용합니다.

 

파라매트릭 서치는 이분탐색과 큰 차이는 없으며,

이분탐색이 정확히 M인 값을 구하는 반면, 파라매트릭 서치는 M에 가장 가까운 최적의 값을 구하는 것입니다.

 

 

이 문제는 두 가지 방법을 선택하여 해결할 수 있습니다.

먼저, 모든 김밥에 대해 최적의 P를 구하는 방법입니다.

이 방법은 입력을 그대로 다 받아놓고, 파라매트릭 서치 과정에서 K * 2 or K를 빼는 식이 포함되는 방법입니다.

 

아니면, 애초에 K보다 작거나 K * 2와 같은 길이의 김밥을 먼저 제외하여 최적의 P를 구하는 방법입니다.

이 방법은 입력을 받을 때 미리 K * 2 or K를 빼는 식이 포함되는 방법입니다.

이 과정에서 꼬다리를 제거했을 때 길이가 0 이하가 되는 김밥을 제외합니다.

두 방법 모두 AC를 받는데는 문제가 없으나 두번째 방법이 더 적은 갯수로 구할 수 있으므로 시간상 이득을 볼 수 있습니다.

 

파라매트릭 과정에서 필요없는 김밥을 제외
입력 과정에서 필요없는 김밥을 제외

두 방법으로 제출했을 때 확실히 미리 제외한 방법이 시간상 효율적이었습니다.

 

파라매트릭 서치 과정에서는

l, r은 김밥조각의 길이인 P의 범위이며, 김밥을 m으로 나눈 몫을 카운팅한 값이 M 이상이 되는 최적의 해를 구해주시면 되겠습니다.

 

 

[필요없는 김밥을 제외하지 않은 코드]

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>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> list;
int N, K, M, l, r;
 
void func() {
    int ans = -1;
    l = 1;
    while (l <= r) {
        int m = (l + r) >> 1;
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] <= K) continue;
 
            if (list[i] >= K * 2) cnt += ((list[i] - K * 2) / m);
            else cnt += ((list[i] - K) / m);
        }
 
        if (cnt >= M) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    int x;
    cin >> N >> K >> M;
    for (int i = 0; i < N; i++) {
        cin >> x;
 
        list.push_back(x);
        r = max(r, x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

[처음부터 필요없는 김밥을 제외한 코드]

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> list;
int N, K, M, l, r;
 
void func() {
    int ans = -1;
    l = 1;
    while (l <= r) {
        int m = (l + r) >> 1;
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            cnt += (list[i] / m);
        }
 
        if (cnt >= M) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    int x;
    cin >> N >> K >> M;
    for (int i = 0; i < N; i++) {
        cin >> x;
        if (x <= K || x == K * 2) continue;
 
        int sub = x;
        if (x < K * 2) sub -= K;
        else sub -= (K * 2);
 
        list.push_back(sub);
        r = max(r, sub);
    }
 
    N = list.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > binarysearch' 카테고리의 다른 글

boj 27977 킥보드로 등교하기  (4) 2023.04.22
boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22

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

M개의 공유기를 놓을 수 있는 최대한의 간격을 구하는 문제입니다.

최대한의 간격은 최적화된 정답을 구하는 것이므로 파라매트릭 서치로 해결합니다.

 

우선 이분탐색을 쓰기 위해 입력받은 위치정보를 정렬합니다.

탐색 범위는 간격이며, (1 ~ list[N] - list[1])의 범위에서 탐색합니다.

 

간격 m에서 공유기를 M개 이상 놓을 수 있는지 확인합니다.

놓을 수 있으면 true, 아니면 false를 리턴합니다.

 

solve함수의 리턴 값이 true면 ans에 현재 간격을 저장하고 (m + 1 ~ r) 범위를 탐색합니다.

solve함수의 리턴 값이 false면 (s ~ m - 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[200001];
int N, M;
 
bool solve(int length) {
    int pre = list[1];
    int cnt = 1;
    for (int i = 2; i <= N; i++) {
        if (list[i] - pre >= length) {
            cnt++;
            pre = list[i];
        }
    }
 
    if (cnt >= M) return true;
    else return false;
}
 
int binarySearch(int l, int r) {
    int ans = 0;
 
    while (l <= r) {
        int m = (l + r) / 2;
        if (solve(m)) {
            ans = m;
            l = m + 1;
        }
        else r = m - 1;
    }
 
    return ans;
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    sort(list + 1, list + 1 + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << binarySearch(1, list[N] - list[1]) << '\n';
 
    return 0;
}
 cs

'algorithm > binarysearch' 카테고리의 다른 글

boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2295 세 수의 합  (0) 2022.06.28
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22

+ Recent posts

티스토리툴바