삼성 SWEA 점심 식사시간

이 문제는 주어진 맵에 사람은 1로 계단은 2이상의 정수로 표현되어 나타난다. 계단은 무조건 2개이며 사람들은 1번 계단 혹은 2번 계단으로 모두 점심 식사를 하러간다. 이 때 계단으로 표현된 2 이상의 정수는 계단을 내려가는 소요시간을 뜻한다. 계단으로 이동하는 소요시간은 계단의 위치를 x,y 사람의 위치를 a,b 라 했을 때 |x-a|+|y-b| 로 표현된다. 동시간에 사람들이 한 계단에 도착할 수 있는데 최대 3명까지밖에 계단을 한 번에 내려갈 수 없다. 즉, 3명이 계단을 내려가고 있는 중이라면 4번 째 오는 사람은 계단에서 대기해야한다.

 계단 입구에 도착하면 1분 후 내려갈 수 있다고 나오는데 애초에 사람과 계단사이의 거리를 구할 때 +1을 해 놓은 상태로 하면 훨씬 편하다.

 사람들이 1 또는 2 번 계단으로 갔을 때를 완전탐색하는 발상은 쉬웠지만 계단을 모두 내려갈 때까지의 소요시간을 구하는 것이 힘들었다. 구현을 못하겠떠... 어찌저찌 인터넷 코드를 참조하며 코딩했다.

calc 함수 설명

1번 계단을 이용할 경우

정렬된 상태의 vector 가 들어온다. vector 안에는 1번 계단을 이용한 사람들의 도착시간이 담겨져있다.

time 변수를 첫 번째 백터값으로 설정한다.

time 보다 같거나 작은 벡터 값만 space 에 넣으면서 동시간에 도착한 사람들이 최대 3명만 들어갈 수 있도록 한다.

space 배열이 0보다 같거나 작다면 비어있다고 판단, 계단의 소요시간을 넣는다.

벡터의 마지막 요소일 경우 현재까지 시간(time)에 계단 소요시간을 더한 뒤 리턴한다.

한 루프를 돈 후 space 배열의 값들을 전부 -1 시켜준다.

반복한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
 
vector <int> choice;
int ans = 0;
int calc(vector<int> &v, int t) {
    if (v.size() == 0) return 0;
 
    int time = v[0];
    int space[3] = {0,0,0};
    
    while (1) {
        for (int i = 0; i < v.size(); i++) {
            if (v[i] == 0) continue;
 
            if (v[i] <= time) {
                for (int j = 0; j < 3; j++) {
                    if (space[j] <= 0) {
                        space[j] = t;
                        v[i] = 0;
                        if (i == v.size() - 1) { return time + t; }
                        break;
                    }
                }
            }
        }
        
        for (int i = 0; i < 3; i++) {
            space[i]--;
        }
        time++;
    }
}
void solve(vector <vector <int> > &map, vector <pair<int, int > > &person, vector <tuple<int, int, int> > &stair, int cnt) {
    if (cnt == person.size()) {
        vector <int> s1; vector <int> s2;
        for (int i = 0; i < choice.size(); i++) {
            if (choice[i] == 0) { 
                int len = abs(person[i].first - get<0>(stair[0])) + abs(person[i].second - get<1>(stair[0])) + 1;
                s1.push_back(len);
            }
            else {
                int len = abs(person[i].first - get<0>(stair[1])) + abs(person[i].second - get<1>(stair[1])) + 1;
                s2.push_back(len);
            }
        }
        
        sort(s1.begin(), s1.end());
        int sum = calc(s1, get<2>(stair[0]));
        sort(s2.begin(), s2.end());
        int sum2 = calc(s2, get<2>(stair[1]));
        
        if (ans > max(sum, sum2)) { 
            ans = max(sum, sum2); 
        }
        return;
    }
 
    for (int i = 0; i < stair.size(); i++) {
        choice.push_back(i);
        solve(map, person, stair, cnt+1);
        choice.pop_back();
    }
}
 
int main() {
    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        int N; cin >> N;
        ans = 987654321;
        vector <vector <int> > map(N+1, vector<int>(N+1));
        
        vector <pair<int, int > > person;
        vector <tuple<int, int, int> > stair;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> map[i][j];
                if (map[i][j] == 1) person.push_back({ i,j });
 
                if (map[i][j] >= 2)stair.push_back(make_tuple(i, j, map[i][j]));
            }
        }
        
        solve(map, person, stair,0);
 
        cout << "#"<<t<<' '<<ans << '\n';
 
    }
    return 0;
}