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

 

1 ~ N번 방은 서로 원형으로 연결되어 있으며, 각 방에는 Ci개의 쪽방이 있을 수 있습니다.

통로로 직접 연결되어 있는 두 방에는 하나의 개미만 들어갈 수 있으며, 개미굴에 살고있는 개미의 최대 수를 구하는 문제입니다.

 

문제의 카테고리가 dp와 그리디가 있었지만 저는 그리디로 해결했습니다.

우선 쪽방이 있다면 무조건 들어가는 것이 이득입니다.

쪽방은 i번 방의 바로 아래에 있는 자식 노드기 때문에 쪽방의 갯수를 세어주도록 합니다.

 

그 다음은 쪽방이 없는 나머지 방을 세어줍니다.

나머지 방에는 연속된 방으로 세어주시고, (연속된 방의 갯수 (cnt) + 1) / 2으로 구할 수 있습니다.

 

그것들을 정답에 더해주시면 되는데 마지막으로 생각할게 개미굴은 원형으로 되어있기 때문에 1번과 N번 방이 서로 연결되어 있습니다.

순회를 1번 방부터 했기 때문에 만약 1번과 N번 방 둘다 쪽방이 없다면 연속된 방의 갯수들을 합쳐줘야 합니다. (cnt + tmp)

그걸 위해서 처음에 1번 방부터 isFirst 변수를 추가하여 처음 연속된 빈방의 갯수를 tmp에 저장해두었습니다.

 

 

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
#include <iostream>
#define MAX 250001
using namespace std;
typedef long long ll;
 
ll list[MAX];
bool flag;
int N;
 
void func() {
    if (!flag) {
        cout << (N >> 1<< '\n';
        return;
    }
 
    ll ret = 0;
    ll cnt = 0;
    ll tmp = 0;
    bool isFirst = true;
    for (int i = 0; i < N; i++) {        
        if (!list[i]) cnt++;
        else {
            if (isFirst) tmp = cnt;
            ret += list[i];
            isFirst = false;
            ret += ((cnt + 1LL) >> 1);
            cnt = 0;
        }
    }
 
    if (!list[0&& !list[N - 1]) {
        ret -= ((tmp + 1LL) >> 1);
        ret += ((tmp + cnt + 1LL) >> 1);
    }
    else ret += ((cnt + 1LL) >> 1);
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        flag |= list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

소는 A ~ B 시간 사이에만 이동할 수 있고, 닭은 T 시간에만 도움을 줄 수 있습니다.

즉 A <= T <= B 가 되어야 닭이 소를 도와줄 수 있습니다.

 

구현은 간단합니다.

가장 빠르게 도움을 줄 수 있는 닭을 찾기 위해 닭은 오름차순으로 정렬합니다.

그리고 소는 끝시간 기준 오름차순으로 정렬합니다.

이후에는 소 한마리씩 순회하여 도움을 받을 적절한 닭을 찾아주시면 됩니다.

 

범위가 각각 2만이기 때문에 TLE가 나오지 않을까 생각했지만 N * M으로도 풀리는 문제였습니다.

아마 중간에 적절한 답을 찾으면 break를 해주면서 시간이 어느정도 단축되는 것으로 보입니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 20001
using namespace std;
typedef pair<intint> pii;
 
int list[MAX];
pii cow[MAX];
int N, M;
 
void func() {
    sort(list, list + N);
    sort(cow, cow + M, [](pii a, pii b) {
        return a.second < b.second;
    });
 
    int ret = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (list[j] == -1continue;
            if (cow[i].first > list[j] || list[j] > cow[i].second) continue;
 
            ret++;
            list[j] = -1;
            break;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
 
    for (int i = 0; i < M; i++) {
        cin >> cow[i].first >> cow[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

문제를 보자마자 6068번 시간 관리하기 문제랑 같다는 것을 느꼈습니다.

마감 시간(Si)과 일을 하는데 걸리는 시간(Ti)이 주어지고, 언제부터 시작하면 일을 끝낼 수 있는지 구해야 합니다.

마감 시간 기준 내림차순으로 정렬하여 뒤에서부터 탐색한다면 쉽게 해결할 수 있습니다.

저는 혹시 몰라서 Si가 같다면 Ti 기준으로도 정렬을 했지만 생각해보니 그럴 필요는 없어보입니다.

 

시간을 최대로 세팅을 먼저 하고, 내려가면서 Ti를 빼주시면 되겠습니다.

도중에 현재 작업의 Si보다 t가 더 크다면 Si로 현재 시간을 조정해주시면서 진행해주시면 됩니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
typedef pair<intint> pii;
 
pii list[MAX];
int N;
 
bool cmp(pii a, pii b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
void func() {
    sort(list, list + N, cmp);
 
    int t = 1e9;
    for (int i = 0; i < N; i++) {
        t = min(t, list[i].second);
        t -= list[i].first;
 
        if (t < 0) {
            cout << "-1\n";
            return;
        }
    }
 
    cout << t << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

다이아 문제중에 해볼만한 문제로 가져와봤습니다.

 

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i + 1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i + 1)번 공장, (i + 2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 2). 이 경우 비용은 7원이 든다.

우선 라면을 구매할 수 있는 방법은 이렇게 3가지입니다.

 

i번째 공장에서는 남아있는 모든 라면을 구매하는게 맞겠고,

i + 1, i + 2번째 공장의 라면을 가능하면 추가로 구매하는게 더 좋습니다.

제가 구현한 방식은 i번째 라면은 개당 3원씩 모두 구매하고, i + 1, i + 2번째 라면을 구매할때마다 2원을 추가하는 방식으로 구현했습니다.

 

하지만 i ~ i + 2 범위 내에 가능한 모든 라면을 구매한다면 반례가 존재합니다.

4
1 2 1 1

여기서 가능한대로 모든 라면을 구매한다고 했을 때 1 ~ 3번째 공장에서 라면을 구매했을 것입니다. (소모한 금액: 7)

0 1 0 1

그러면 남은 라면은 이렇게 될 것이고, 남은 공장에서 하나씩 구매한다면 7 + 3 + 3 = 13의 금액이 필요합니다.

 

 

하지만 처음에 3번 공장에서 구매하지 않는다면

0 1 1 1

1, 2번째 공장에서만 라면을 구입하고, (소모한 금액: 5)

나머지 2 ~ 4번째 공장에서 라면을 구입한다면 5 + 7 = 12의 금액이 필요하여 이게 최소가 됩니다.

 

따라서 하나더 고려해야할 부분은 최초 필요한 갯수가 list[i + 1] > list[i + 2] 이라면

"i + 1번째 공장에서 남긴 수만큼 i + 2번째 공장에서도 남겨야 한다"가 됩니다.

물론 i + 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
#include <iostream>
#include <algorithm>
#define MAX 10010
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        if (!list[i]) continue;
        int cnt = list[i];
        list[i] = 0;
        ret += (3 * cnt);
 
        if (i + 1 >= N) continue;
        cnt = min(cnt, list[i + 1]);
        list[i + 1-= cnt;
        ret += (2 * cnt);
 
        if (i + 2 >= N) continue;
        if (cnt + list[i + 1> list[i + 2]) {
            cnt = min(cnt, max(0, list[i + 2- list[i + 1]));
        }
        list[i + 2-= cnt;
        ret += (2 * cnt);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30

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

 

16120번: PPAP

첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

www.acmicpc.net

P는 PPAP 문자열이며, P를 PPAP로 바꾼 문자열 역시 PPAP 문자열입니다.

이 조건과 문자열 주어졌을 때 PPAP 문자열인지 판별하는 문제입니다.

 

우선 문자열의 처음부터 순회를 합니다.

해당 위치의 문자가

'P'이면 cnt를 1 증가합니다.

'A'이면 cnt가 2 이상이고, 다음 문자가 'P'이면 PPAP문자열이므로 PPAP를 P로 변경합니다.

실제 로직으로는 cnt를 1 감소하고, 다음 인덱스가 P인것을 확인했으니 인덱스도 1 증가합니다.

만약 'A'일때 cnt가 2보다 작거나, 마지막 인덱스이거나, 다음 문자가 'P'가 아니면 NP를 출력합니다.

 

순회가 끝났을때 남는 문자열은 P여야하므로 cnt가 1일때만 PPAP를 출력, 아니면 NP를 출력합니다.

 

 

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
#include <iostream>
#include <string>
using namespace std;
 
string str;
int N;
 
void func() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (str[i] == 'P') cnt++;
        else {
            if (cnt >= 2 && i < N - 1 && str[i + 1== 'P') {
                cnt--;
                i++;
            }
            else {
                cout << "NP\n";
                return;
            }
        }
    }
 
    if (cnt == 1cout << "PPAP\n";
    else cout << "NP\n";
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22

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

 

2262번: 토너먼트 만들기

월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러

www.acmicpc.net

주어지는 랭킹은 중복이 없으며, 랭킹이 높은 사람 (숫자가 낮은 사람)이 무조건 이깁니다.

문제에서 요구하는 것은 이 토너먼트에서 각 경기에 임하는 선수들의 랭킹의 차이의 합이 최소가 되도록 대진을 구성해야합니다.

 

랭킹이 낮을수록 (숫자가 클수록) 랭킹의 차이의 합이 커지므로 랭킹이 낮은 선수는 빠르게 경기를 하는 것이 이득입니다.

따라서 랭킹이 낮은 선수부터 차례대로 본인의 좌우 선수들 중 랭킹이 낮은 선수와 경기를 하게 만들면 랭킹의 차이의 합이 최소가 됩니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 256
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ans = 0;
    for (int i = N; i > 1; i--) {
        int j = 0;
        for (; j <= N; j++) {
            if (i == list[j]) break;
        }
 
        ans += (i - max(list[j - 1], list[j + 1]));
 
        for (; j < N; j++) {
            list[j] = list[j + 1];
        }
        N--;
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16

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

 

13904번: 과제

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

www.acmicpc.net

그리디는 많이 안풀어봐서 어렵네요..

이 문제는 정렬 + 그리디 문제입니다.

 

우선 마감일, 과제 점수를 담은 list배열을

  1. 과제 점수가 높은 순 (내림차순)
  2. 마감일이 적게 남은 순 (오름차순)

으로 정렬합니다.

 

그 다음 과제 점수가 가장 높은 0번 인덱스부터 과제를 진행합니다.

여기서 확인해야할 것은 마감일 안에 과제를 할 수 있는지에 대한 여부입니다.

d일부터 1일까지 visit[d]=true인지 확인해서 해당 일에 과제를 했는지 체크합니다.

과제를 했다면 전날 과제를 했는지 체크하는 방식으로 1일까지 확인합니다.

 

과제를 하지않은 날이 있다면 과제를 진행하고 방문체크 해주면 되고,

d ~ 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
#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;
typedef pair<intint> pi;
 
pi list[MAX];
bool visit[MAX + 1];
int N;
 
bool cmp(pi a, pi b) {
    if (a.second == b.second) return a.first < b.first;
    else return a.second > b.second;
}
 
void func() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int d = list[i].first;
        for (int j = d; j > 0; j--) {
            if (visit[j]) continue;
            
            visit[j] = true;
            ans += list[i].second;
            break;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    sort(list, list + N, cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

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

boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16

www.acmicpc.net/problem/1826

 

1826번: 연료 채우기

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경

www.acmicpc.net

1km를 가는데 연료가 1L씩 소모됩니다.

목적지까지 가는 길에 주유소가 있어서 부족한 연료를 채우고 가야합니다.

마을에 도착했을 때, 주유소를 방문한 최소 횟수를 출력하는 문제입니다. 만약 목적지에 도착하지 못하면 -1을 출력합니다.

 

저는 거리 1당 1L이므로 연료소모를 하지않고 계속 쌓으면서 목적지까지 갈 수 있는지 확인하였고, 방법은 그리디로 하였습니다.

우선 입력으로 주어지는 주유소의 정보를 거리기준으로 오름차순 정렬합니다.

그 다음 현재 연료로 갈 수 있는 지점까지 큐에 넣어주면서 이동하다가

연료보다 더 멀리있는 주유소가 나오면 지금까지 큐에 넣어두었던 연료 중 가장 높은 값을 저장합니다.

물론 이를 위해 우선순위 큐를 사용합니다.

 

이 연산을 반복하여 마지막 목적지를 기준으로 연료가 충분한지도 확인해야합니다.

충분하면 그대로 ans를 출력, 모든 주유소를 다 들려도 목적지에 가지 못하면 -1을 출력합니다.

 

 

[C++]

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 <algorithm>
#include <queue>
using namespace std;
 
priority_queue<int> q;
pair<intint> list[10001];
int N, des, now, ans;
 
void func() {
    int idx = 0;
    while (idx < N) {
        if (now >= list[idx].first) {
            q.push(list[idx].second);
        }
        else {
            if (q.empty()) break;
            now += q.top();
            q.pop();
            ans++;
            idx--;
        }
        idx++;
    }
    while (!q.empty()) {
        if (now >= des) break;
        
        now += q.top();
        q.pop();
        ans++;
    }
 
    if (now >= des) cout << ans << '\n';
    else cout << "-1\n";
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    cin >> des >> now;
    sort(list, list + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N, des, now, ans;
 
    static void func() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int idx = 0;
        while (idx < N) {
            if (now >= list[idx][0])
                q.add(-list[idx][1]);
            else {
                if (q.isEmpty())
                    break;
 
                now -= q.poll();
                ans++;
                idx--;
            }
            idx++;
        }
 
        while (!q.isEmpty()) {
            if (now >= des)
                break;
            now -= q.poll();
            ans++;
        }
 
        if (now >= des)
            System.out.println(ans);
        else
            System.out.println(-1);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0= Integer.parseInt(st.nextToken());
            list[i][1= Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        des = Integer.parseInt(st.nextToken());
        now = Integer.parseInt(st.nextToken());
 
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0- b[0];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16

 

www.acmicpc.net/problem/8980

 

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

처음에는 보내는 마을 기준으로 오름차순 정렬하였으나, 반례를 만나고 소스를 갈아엎고 받는 마을 기준으로 오름차순 정렬하였습니다.

 

우선 to배열에는 해당 마을을 지날때 최대용량으로 초기화를 시켜놓았습니다.

다음은 예제로 설명을 하겠습니다.

4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20

N = 4, C = 40, M = 6

택배 정보를 받는 마을 기준으로 정렬하면 이렇게됩니다. to[1] = 40, to[2] = 40, to[3] = 40

1 2 10
1 3 20
2 3 10
1 4 30
2 4 20
3 4 20

이제 1 -> 2로 10만큼을 보냅니다.

도착마을인 2를 제외하고 1 -> 2 경로에 있는 마을의 남은 용량의 최소는 40으로 10보다 큽니다.

그러면 to[1]에서 10만큼 빼줍니다.

(ans = 10)

to[1] = 30, to[2] = 40, to[3] = 40

 

다음 1 -> 3으로 20만큼 보냅니다.

도착마을인 3을 제외하고 1 -> 3 경로에 있는 마을의 남은 용량의 최소는 30으로 20보다 큽니다.

그러면 to[1]와 to[2]에서 20만큼 빼줍니다.

(ans = 10 + 20 = 30)

to[1] = 10, to[2] = 20, to[3] = 40

 

다음 2 -> 3으로 10만큼 보냅니다.

도착마을인 3을 제외하고 2 -> 3 경로에 있는 마을의 남은 용량의 최소는 20으로 10보다 큽니다.

그러면 to[2]에 10만큼 빼줍니다.

(ans = 30 + 10 = 40)

to[1] = 10, to[2] = 10, to[3] = 40

 

다음 1 -> 4로 30만큼 보냅니다.

도착마을인 4를 제외하고 1 -> 4 경로에 있는 마을의 남은 용량의 최소는 10으로 30보다 작습니다.

따라서 남은 용량의 최소만큼인 10만큼 빼줍니다.

(ans = 40 + 10 = 50)

to[1] = 0, to[2] = 0, to[3] = 40

 

다음 2 -> 4로 20만큼 보냅니다.

도착마을인 4를 제외하고 2 -> 4 경로에 있는 마을의 남은 용량의 최소는 0이므로 보낼 수 없습니다.

(ans = 50)

to[1] = 0, to[2] = 0, to[3] = 40

 

다음 3 -> 4로 20만큼 보냅니다.

도착마을인 4를 제외하고 3 -> 4 경로에 있는 마을의 남은 용량의 최소는 40으로 20보다 큽니다.

그러면 to[3]에 20만큼 빼줍니다.

(ans = 70)

to[1] = 0, to[2] = 0, to[3] = 20

 

과정이 모두 끝났으니 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<int[]> list = new ArrayList<>();
    static int to[];
    static int N, C, M, ans;
 
    static void func() {
        for (int i = 0; i < M; i++) {
            int u = list.get(i)[0];
            int v = list.get(i)[1];
            int c = list.get(i)[2];
 
            int maxC = Integer.MAX_VALUE;
            for (int j = u; j < v; j++)
                maxC = Math.min(maxC, to[j]);
 
            if (maxC >= c) {
                for (int j = u; j < v; j++)
                    to[j] -= c;
                ans += c;
            } else {
                for (int j = u; j < v; j++)
                    to[j] -= maxC;
                ans += maxC;
            }
        }
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int u, v, c;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        to = new int[N + 1];
        Arrays.fill(to, C);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            list.add(new int[] { u, v, c });
        }
 
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1== b[1])
                    return a[0- b[0];
                else
                    return a[1- b[1];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16

www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

www.acmicpc.net

N개의 수업이 주어지면 강의실을 최소로 사용해서 모든 수업을 해야합니다.

저는 강의 시작시간 기준으로 정렬하였고, 우선순위 큐에 강의 종료시간을 넣었습니다.

 

q.peek()은 현재 진행중인 강의 중 가장 빠르게끝나는 강의이며, 다음 진행할 강의와 비교를 합니다 (x <= list[i][0])

x <= list[i][0]이면 같은 강의실에서 강의를 할 수 있으므로 remove를 해줍니다.

강의는 무조건 해야하므로 마지막에 끝나는 시간을 add 해줍니다.

마지막으로 q의 크기를 출력하시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N;
 
    static void func() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(list[0][1]);
        for (int i = 1; i < N; i++) {
            int x = q.peek();
 
            if (x <= list[i][0])
                q.remove();
            q.add(list[i][1]);
        }
 
        System.out.println(q.size());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0= Integer.parseInt(st.nextToken());
            list[i][1= Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0== b[0])
                    return a[1- b[1];
                else
                    return a[0- b[0];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29

www.acmicpc.net/problem/1931

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

회의실이 1개이고, 이를 사용할 수 있는 회의의 최대 갯수를 출력하는 문제입니다.

저는 회의 종료시간 기준으로 정렬한 후 그리디로 해결하였습니다.

 

회의 종료시간을 유지하면서 다음 회의부터 N까지 순회를 합니다.

현재 회의 종료시간이 다음 회의의 시작시간보다 작거나 같을때마다 종료시간을 갱신하고, ans를 1 늘려줍니다.

N번까지 순회 이후 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N, ans = 1;
 
    static void func() {
        int e = list[0][1];
        for (int i = 1; i < N; i++) {
            if (e <= list[i][0]) {
                e = list[i][1];
                ans++;
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0= Integer.parseInt(st.nextToken());
            list[i][1= Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1== b[1]) {
                    if (a[0< b[0])
                        return -1;
                    else
                        return 1;
                } else {
                    if (a[1< b[1])
                        return -1;
                    else
                        return 1;
                }
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29
boj 1339 단어 수학  (0) 2021.01.22

www.acmicpc.net/problem/2839

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

설탕 Nkg을 3kg 봉지와 5kg 봉지로 담는 그리디 문제입니다.

봉지가 담을 수 있는 무게가 3, 5 kg으로 한정되어있으니 설탕의 무게는 (3의배수 + 5의배수) kg이 됩니다.

 

우선 5kg이 가장 크기때문에 N이 5로 나누어떨어지면 모든 설탕을 5kg에 담으면 됩니다.

그렇지 않으면 3kg씩 빼주면서 다시 N이 5로 나누어떨어지는지 확인하는 방식으로 구현하였습니다.

 

만약 위의 과정에서 N이 5보다 작고 3의배수가 아니면 -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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
 
    static void func() {
        int ans = 0;
        while (true) {
            if (N % 5 == 0) {
                ans += (N / 5);
                N = 0;
            } else {
                ans++;
                N -= 3;
            }
 
            if (N == 0)
                break;
            
            if (N < 5 && N % 3 != 0) {
                ans = -1;
                break;
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29
boj 1339 단어 수학  (0) 2021.01.22

+ Recent posts