ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #2383 _ 점심 식사시간
    Problem Solving/SWEA 2019. 10. 29. 18:57

    [점심 식사시간] https://swexpertacademy.com/main/code/problem/problemDetail.do

     

    SW Expert Academy

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

    swexpertacademy.com

    사람이 1번 계단을 이용하는 경우2번 계단을 이용하는 경우 두 가지의 경우를 고려할 수 있다.

    이는 chk 배열을 이용하여 구현하였다.

     

    s_1과 s_2는 1번 계단과 2번 계단을 이용하는 사람을 저장하는 벡터이고,

    val은 계단과 사람의 거리이다.

    (거리가 짧을 수록 먼저 도착하기 때문)

     

    계단을 이용할 수 있는 모든 방법의 시간을 계산하여 최소 시간을 구하였다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <cmath>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #define MAX 10
    
    using namespace std;
    
    int N, map[MAX][MAX], minVal, chk[10];
    vector<pair<int, int> > person, stair;
    
    void init();
    void solve(int idx);
    int getTime();
    int main() {
    	int test_case;
    	scanf("%d", &test_case);
    	for (int i = 1; i <= test_case; i++) {
    		scanf("%d", &N);
    
    		init();
    
    		for (int j = 0; j < N; j++) {
    			for (int k = 0; k < N; k++) {
    				scanf("%d", &map[j][k]);
    				if (map[j][k] == 1) person.push_back(make_pair(j, k));
    				else if (map[j][k] >= 2) stair.push_back(make_pair(j, k));
    			}
    		}
    		solve(0);
    
    		printf("#%d %d\n", i, minVal);
    	}
    
    	return 0;
    }
    
    void init() {
    	for (int i = 0; i < N; i++) chk[i] = 0;
    	minVal = 9999999;
    	person.clear();
    	stair.clear();
    }
    
    void solve(int idx) {
    	if (idx >= person.size()) {
    		minVal = min(minVal, getTime());
    		return;
    	}
    	chk[idx] = 1;
    	solve(idx + 1);
    	chk[idx] = 2;
    	solve(idx + 1);
    }
    
    int getTime() {
    	vector<int> s_1, s_2;
    	queue<int> e_1, e_2, tmp_q;
    	int val, tmp, time = 0;
    
    	for (int i = 0; i < person.size(); i++) { // 각 계단에 사람 배치
    		if (chk[i] == 1) {
    			val = abs(stair[0].first - person[i].first) + abs(stair[0].second - person[i].second);
    			s_1.push_back(val);
    		}
    		else {
    			val = abs(stair[1].first - person[i].first) + abs(stair[1].second - person[i].second);
    			s_2.push_back(val);
    		}
    	}
    	
    	sort(s_1.begin(), s_1.end());
    	sort(s_2.begin(), s_2.end());
    
    	while (1) {
    		time++;
    		if (s_1.size() == 0 && s_2.size() == 0 && e_1.empty() && e_2.empty()) break;
    
    		int s = s_1.size();
    		for (int i = 0; i < s; i++) {
    			tmp = s_1.front();
    			s_1.erase(s_1.begin());
    			if (tmp <= time) e_1.push(map[stair[0].first][stair[0].second] + 1);
    			else s_1.push_back(tmp);
    		}
    
    		s = s_2.size();
    		for (int i = 0; i < s; i++) {
    			tmp = s_2.front();
    			s_2.erase(s_2.begin());
    			if (tmp <= time) e_2.push(map[stair[1].first][stair[1].second] + 1);
    			else s_2.push_back(tmp);
    		}
    
    		// 한번에 계단을 이용할 수 있는 사람 수는 3명
    		int cnt = 0;
    		s = e_1.size();
    		for (int i = 0; i < s; i++) {
    			if (cnt < 3) tmp = e_1.front() - 1;
    			else tmp = e_1.front();
    			e_1.pop();
    
    			if (tmp > 0) e_1.push(tmp);
    			else cnt--;
    
    			cnt++;
    		}
    
    		cnt = 0;
    		s = e_2.size();
    		for (int i = 0; i < s; i++) {
    			if (cnt < 3) tmp = e_2.front() - 1;
    			else tmp = e_2.front();
    			e_2.pop();
    
    			if (tmp > 0) e_2.push(tmp);
    			else cnt--;
    
    			cnt++;
    		}
    	}
    
    	return time;
    }

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

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

    댓글

@Jo Grini's Blog