ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #2477 _ 차량 정비소
    Problem Solving/SWEA 2019. 10. 29. 19:14

    [차량 정비소] https://swexpertacademy.com/main/code/problem/problemDetail.do

     

    SW Expert Academy

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

    swexpertacademy.com

    tk는 도착한 시간을 저장하는 큐로 손님의 수만큼 값을 저장한다.

    v_a, v_b는 a창구와 b창구 이용하는 손님을 가지는 벡터이다.

     

    checkPossible() 함수는 사용 가능한 창구 번호를 반환해준다.

    tk가 현재 시간인 time보다 작거나 같아지면, 손님이 도착한 것이기 때문에 wait 큐에 넣어준다.

    (이때, wait은 우선순위 큐를 이용하여 손님의 우선 순위대로 pop 되도록 구현하였다.)

     

    시간이 흐르다 사용 가능한 b창구가 생기면 wait 큐에서 반환된 손님이 창구를 이용한다.

    getSumNumber() 함수를 이용하여, 주어진 창구에서 이용한 손님의 합을 구하였다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #define MAX 10
    
    using namespace std;
    
    typedef struct person {
    	int number = 0;
    	int a_num = 0;
    	int b_num = 0;
    	int time = -1;
    }Person;
    
    struct cmp {
    	bool operator()(Person a, Person b) {
    		if (a.time == b.time) {
    			return a.a_num > b.a_num;
    		}
    		else return a.time > b.time;
    	}
    };
    
    int N, M, K, A, B, num = 1;
    int a[MAX], b[MAX], chk_a[MAX], chk_b[MAX];
    vector<int> tmp_tk;
    queue<int> tk;
    queue<Person> person_q;
    
    void init();
    void solve();
    int checkPossible(int a_b);
    int getSumNumber();
    int main() {
    	int T, tmp, result;
    
    	scanf("%d", &T);
    	for (int i = 1; i <= T; i++) {
    		scanf("%d %d %d %d %d", &N, &M, &K, &A, &B);
    		for (int j = 1; j <= N; j++) scanf("%d", &a[j]);
    		for (int j = 1; j <= M; j++) scanf("%d", &b[j]);
    		for (int j = 0; j < K; j++) {
    			scanf("%d", &tmp);
    			tk.push(tmp);
    			tmp_tk.push_back(tmp);
    		}
    
    		solve();
    		init();
    
    		result = getSumNumber();
    		if (result == 0) result = -1;
    		printf("#%d %d\n", i, result);
    	}
    	return 0;
    }
    
    void init() {
    	num = 1;
    	for (int i = 1; i <= N; i++) chk_a[i] = 0;
    	for (int i = 1; i <= M; i++) chk_b[i] = 0;
    	tmp_tk.clear();
    }
    
    void solve() {
    	vector<Person> v_a, v_b;
    	priority_queue<Person, vector<Person>, cmp> wait;
    	Person tmp;
    	int check, time = 0;
    
    	while (!tk.empty()) {
    		for (int i = 0; i < v_b.size(); i++) {
    			v_b[i].time--;
    			if (v_b[i].time <= 0) {
    				chk_b[v_b[i].b_num] = 0;
    				tk.pop();
    				person_q.push(v_b[i]);
    				v_b.erase(v_b.begin() + i);
    				i--;
    			}
    		}
    
    		for (int i = 0; i < v_a.size(); i++) {
    			v_a[i].time--;
    			if (v_a[i].time <= 0) {
    				chk_a[v_a[i].a_num] = 0;
    				v_a[i].time = time;
    				wait.push(v_a[i]);
    				v_a.erase(v_a.begin() + i);
    				i--;
    			}
    		}
    
    		while (!wait.empty()) {
    			check = checkPossible(0);
    			if (check > 0) {
    				tmp = wait.top();
    				wait.pop();
    				chk_b[check] = 1;
    				tmp.b_num = check;
    				tmp.time = b[check];
    				v_b.push_back(tmp);
    			}
    			else break;
    		}
    
    		while (num <= K) {
    			if (tmp_tk[num - 1] > time) break;
    			check = checkPossible(1);
    			if (check > 0) {
    				chk_a[check] = 1;
    				tmp.number = num++;
    				tmp.a_num = check;
    				tmp.time = a[check];
    				v_a.push_back(tmp);
    			}
    			else break;
    		}
    		time++;
    	}
    
    }
    
    int checkPossible(int a_b) {
    	if (a_b == 1) {
    		for (int i = 1; i <= N; i++) if (!chk_a[i]) return i;
    	}
    	else {
    		for (int i = 1; i <= M; i++) if (!chk_b[i]) return i;
    	}
    
    	return 0;
    }
    
    int getSumNumber() {
    	Person tmp;
    	int result = 0;
    
    	while (!person_q.empty()) {
    		tmp = person_q.front();
    		person_q.pop();
    
    		if (tmp.a_num == A && tmp.b_num == B) result += tmp.number;
    	}
    
    	return result;
    }

    'Problem Solving > SWEA' 카테고리의 다른 글

    [SWEA] #4008 _ 숫자 만들기  (0) 2019.10.29
    [SWEA] #2477 _ 차량 정비소  (0) 2019.10.29
    [SWEA] #2383 _ 점심 식사시간  (0) 2019.10.29
    [SWEA] #2382 _ 미생물 격리  (0) 2019.10.29
    [SWEA] #2117 _ 홈 방범 서비스  (0) 2019.10.29
    [SWEA] #2115 _ 벌꿀채취  (0) 2019.10.29

    댓글 0

@Jo Grini's Blog :)