ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2477.차량 정비소
    알고리즘/SW Expert Academy 2020. 7. 7. 23:56

    오랜만에 문제를 풀었다. 그 동안 했던 것 중에 잘 모르겠던거 복습도하고 충분한 휴식도 취하고 왔다. 이제 다시 달려야지!!

    이번에 풀어볼 문제는 SW Expert의 2477번 문제 차량 정비소이다.

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    생각보다 굉장히 까다로운 시뮬레이션이고 이 문제는 설계를 망치면 그냥 꼬여버리는 문제이다.

    설계만 잘한다면 난이도는 그리 높지 않다. 그럼에도 1시간 29분 정도 걸렸다. 너무 헷갈려..ㅠ

     

    이 문제를 푸는 포인트는 생각해보면 굉장히 간단하다. 

    1. 대기열을 생각해줘야한다.

     => 바로 고객이 도착해서 접수 창구로 가는 사이에 waiting하는 대기열

     => 접수창구에서 정비창구로가는 waiting 대기열을 생각해주고 설계히면 된다.

     

    2. 둘다 들리는 경우를 체크해주면된다.

    => 배열을 하나 선언해서 A와 B 창구를 들린 고객번호의 index의 값 더해 2가 나오면 둘 다 거쳐간 것으로 체크하였다.

     

     


     

    < Code 설명 >

    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
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <deque>
    #include <string.h>
     
    #define MAX 1001
     
    using namespace std;
     
    int T, N, M, K, A, B;
     
    int answer[MAX]; // 접수창구와 정비창구를 거쳤는지 판별하는 배열
     
    deque<pair<intint>>cus; // 고객정보 : 고객번호, 걸린시간
     
    deque<int>wait1; // 대기 큐 ( 도착에서 접수창구 )
    deque<int>wait2; // 대기 큐 ( 접수창구에서 정비창구 )
     
    deque<pair<int,int>>box1; // 고객번호, 소요 시간 => 고객번호가 0이면 고객을 받음 소요시간이 0이면 두 번째 대기큐로 보냄
    deque<pair<int,int>>box2; // 고객번호, 소요 시간 
     
    deque<int> box1_save; // 접수창구 소요시간 저장
    deque<int> box2_save; // 정비창구 소요시간 저장
     
    int ans; // 접수창구와 정비창구를 거친 고객번호 : 정답
     
    void search(){
        int cnt = 0;
        while (true){
            if (cnt == K) // 고객 수가 전부다 업무가 끝나면
                break;// 종료
     
        
            for (int i = 0; i < (int)cus.size(); i++){ // 고객이 도착한 경우 대기 큐에 저장
                if (cus.front().second == 0){ // 고객이 도착한경우
                    wait1.push_back(cus.front().first); // 해당 고객을 첫 번째 대기큐에 저장
                    if (!cus.empty()){ // 고객정보가 비어있지 않았다면
                        cus.pop_front(); // 도착한 고객정보 제거
                        i = -1// 제거 후에는 다시 제일 처음부터 탐색함 ( 도착한 고객이 또 있을 수 있으니 )
                    }
                }
            }
            
     
            for (int i = 0; i < N; i++){ // 접수 창구 수만큼 탐색
                if (box1[i].second == 0){ // 접수창구 소요시간이 다지나면
                    box1[i].second = box1_save[i]; // 접수창수 소요시간 다시 초기화
     
                    if (i + 1 == A) // 우리가 찾는 창구를 이용한 고객이라면
                        answer[box1[i].first] += 1// 방문 고객 idx값 +1
     
                    wait2.push_back(box1[i].first); // 접수창고에서 업무 다봤으니 두 번째 대기큐에 저장
                    box1[i].first = 0// 대기 큐로 보냈으니 접수창구에서는 이용고객 제거
                }
     
                if (box1[i].first == 0 && !wait1.empty()){ // 접수창구가 비어있으면 
                    box1[i].first = wait1.front(); // 접수창구에 대기 큐 제일 앞의 값을 저장    
                    if (!wait1.empty())
                        wait1.pop_front(); // 대기 큐의 제일 앞은 삭제
                }
     
                if (box1[i].first) // 접수창구에 고객이 있으면
                    box1[i].second -= 1// 소요시간 -1
            }
     
            
            for (int i = 0; i < M; i++){ // 정비 창구의 수만큼 탐색
                if (box2[i].second == 0){ // 정비창구 소요시간이 다지나면
                    box2[i].second = box2_save[i]; // 정비창수 소요시간 다시 초기화
     
                    if (i + 1 == B && answer[box2[i].first]==1// 이전에 A창구를 들렸으면서 B창구를 들린 고객이라면
                        answer[box2[i].first] += 1// 방문 고객 idx값 +1
                    
     
                    box2[i].first = 0// 접수창구 이용고객 제거
                    cnt += 1// 고객한명이 완전히 업무를 마치고 나갔으므로 +1
                }
     
                if (box2[i].first == 0 && !wait2.empty()){ // 정비창구가 비어있으면 
                    box2[i].first = wait2.front(); // 정비창구에 대기 큐 제일 앞의 값을 저장    
                    wait2.pop_front(); // 대기 큐의 제일 앞은 삭제
                }
     
                if (box2[i].first) // 정비창구에 고객이 있으면
                    box2[i].second -= 1// 소요시간 -1
            }
     
            for (int i = 0; i < (int)cus.size(); i++// 시간이 지났으므로
                cus[i].second -= 1;  // 고객 도착시간 - 1
        }
        
        for (int i = 1; i <= K; i++){ // A와 B 창구를 거친 고객 idx는 2가 되어있으므로
            if (answer[i]==2// 결과가 2인 배열값만 더해줌
                ans += i;
        }
    }
     
    void init(){ // 초기화
        memset(answer, 0sizeof(answer));
        ans = 0;
        cus.clear();
        wait1.clear();
        wait2.clear();
        box1.clear();
        box2.clear();
        box1_save.clear();
        box2_save.clear();
    }
     
    int main() {
        freopen("2477.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            init();
            cin >> N >> M >> K >> A >> B;
            int tmp;
            for (int i = 0; i < N; i++){
                cin >> tmp;
                box1.push_back(make_pair(0,tmp));
                box1_save.push_back(tmp);
            }
        
            for (int i = 0; i < M; i++){
                cin >> tmp;
                box2.push_back(make_pair(0,tmp));
                box2_save.push_back(tmp);
            }
     
            for (int i = 1; i <= K; i++){
                cin >> tmp;
                cus.push_back(make_pair(i, tmp));
            }
     
            search();
            if (ans == 0// 더해지지 않았다는 것은 우리가 찾는 A,B를 모두 거친 고객이 없다는 것이므로
                cout << "#" << z << " " << -1 << "\n"// -1을 출력
            else
                cout << "#" << z << " " << ans << "\n";// 있다면 결과 출력
        }
        return 0;
    }
    cs

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    2382.미생물격리  (0) 2020.07.21
    2383.점심 식사시간  (0) 2020.07.10
    2477.차량 정비소  (2) 2020.07.07
    2105.디저트 카페  (0) 2020.06.27
    2115.벌꿀채취  (0) 2020.06.23
    4008.숫자 만들기  (0) 2020.06.19

    댓글 2

Designed by Tistory.