반응형

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

 

2513번: 통학버스

첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 좌표와 사람 수의 쌍을 입력받고, 좌표가 S보다 작다면  arr1에, S보다 크다면 arr2에 저장합니다.

 

2. arr1은 좌표를 기준으로 오름차순으로 정렬하고, arr2는 좌표를 기준으로 내림차순으로 정렬합니다.

 

3. 학교를 기준으로 가장 먼 지역부터 버스를 운행해서 해당 좌표에 사람이 K보다 많거나 같다면 왕복 거리를 ans에 더해주고, 나은 사람들을 버스에 태웁니다.

 

4. 3과 마찬가지로 K보다 많거나 같은 사람들을 먼저 처리하고, 버스에 타고 있는 사람 + 현재 좌표에 남은 사람의 수가 K보다 크다면 왕복 거리를 ans에 더해주고, bus의 사람 수를 bus = bus + cnt - K로 저장해 줍니다.

 

5. 3과 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
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N, K, S;
vector<pair<int, int>> arr1;
vector<pair<int, int>> arr2;
 
int main()
{
    scanf("%d %d %d", &N, &K, &S);
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a < S) {
            arr1.push_back({ a,b });
        }
        else {
            arr2.push_back({ a,b });
        }
    }
 
    sort(arr1.begin(), arr1.end());
    sort(arr2.begin(), arr2.end(), greater<>());
 
    int ans = 0;
 
    int bus = 0;
 
    for (auto& next : arr1) {
        const int pos = next.first;
        int cnt = next.second;
 
        if (cnt >= K) {
            ans += (S - pos) * 2 * (int)(cnt / K);
            cnt %= K;
        }
        
        if (cnt > 0) {
            if (bus == 0) {
                ans += (S - pos) * 2;
                bus = cnt;
            }
            else {
                if (bus + cnt > K) {
                    ans += (S - pos) * 2;
                    bus = bus + cnt - K;
                }
                else {
                    bus += cnt;
                }
            }
        }
    }
 
    bus = 0;
 
    for (auto& next : arr2) {
        const int pos = next.first;
        int cnt = next.second;
 
        if (cnt >= K) {
            ans += (pos - S) * 2 * (int)(cnt / K);
            cnt %= K;
        }
 
        if (cnt > 0) {
            if (bus == 0) {
                ans += (pos - S) * 2;
                bus = cnt;
            }
            else {
                if (bus + cnt > K) {
                    ans += (pos - S) * 2;
                    bus = bus + cnt - K;
                }
                else {
                    bus += cnt;
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26
[ 백준 ] 2671번 - 잠수함식별 (C++)  (0) 2023.04.25
[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24

+ Recent posts

티스토리툴바