[SWEZ] 2383 점심 식사시간

2383 점심 식사시간

풀이)

정말 어이없게 시간이 걸린 문제이다.

계단 내려가는 시간을 저장하는 배열(int s_time[2])을 테스트케이스마다 초기화 하지 않아서 틀린건데

방법이 틀려서인줄 알고 계속 고민했다., 그냥 초기화를 안한거...초기화를 잘하자..

풀이과정을 간략히 말하자면 이러하다.

먼저 조합방식(dfs)을 이용해 각 사용자가 어떤 계단을 이용할지 정해줬다.

모든 사용자가 어떤 계단을 사용할지 결정되었다면, 

직접 만든 cal()함수를 통해 시간을 계산해줬다.

cal()함수의 구성은 이러하다

vector <int> time[2]; // 첫번째 계단과 두번째 계단을 이용하기로 한 사용자들이 각자 계단까지 걸리는 시간(이동시간) 저장한 것 

time 벡터를 오름차순으로 정렬하면, 각자 계단마다 언제 사용자가 먼저 도착하고 언제 마지막으로 도착하는지 알 수 있다.

따라서,

각 계단마다 int arr[3]; 세개의 공간을 두고 공간이 비면 사용자를 들여보내고 비지 않으면 사용자를 기다리게 하면서

마지막 사용자가 계단을 완료하는 시간을 구했다.

그리고 

첫번째 계단과 두번째 계단 중 마지막으로 끝나는 시간중 최고값을 최종결과랑 비교했다.

말로 설명하니 좀 어려운데, 코드를 보면서 이해하면 더 편할 것이다.

코드1)

#include <stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
 
#define INF 999999999
 
int n;
int s_time[2]; //계단 내려가는 시간 저장
pair<int, int> stair1, stair2; //계단 위치 저장
vector <pair<int, int>> person; //사람 위치 저장
vector <int> use[2]; //계단을 이용하는 사용자 저장. use[0] = 첫번째 계단을 이용하는 사람의 인덱스들
int result;
 
void cal() {
    int answer = 0;//최종시간
    vector <int> time[2];
 
    //계단 1 입구까지의 이동시간
    for (int i = 0; i < use[0].size(); i++) {
        int tmp= abs(person[use[0][i]].first - stair1.first) + abs(person[use[0][i]].second - stair1.second);
        time[0].push_back(tmp);
    }
    //계단 2 입구까지의 이동시간
    for (int i = 0; i < use[1].size(); i++) {
        int tmp = abs(person[use[1][i]].first - stair2.first) + abs(person[use[1][i]].second - stair2.second);
        time[1].push_back(tmp);
    }
    sort(time[0].begin(), time[0].end());
    sort(time[1].begin(), time[1].end());
    //각 계단 완료하는 시간
    for (int t = 0; t < 2; t++) {
        if (time[t].size() == 0) continue;
        int arr[3] = { 0,0,0 };//계단당 3명까지 수용가능
        int p = 0;//계단이용사람수.
        int cnt = time[t][0];
        while (true)
        {
            
            for (int i = 0; i < 3; i++) {
                if (arr[i] > 0) {
                    arr[i]--;
                    
                }
            }
            
            for (int i = 0; i < 3 && p<use[t].size(); i++) {
                if (arr[i] == 0 && time[t][p] <= cnt) {
                    arr[i] = s_time[t];
                    p++;
                }
            }
            if (p == use[t].size()) {//제일 늦게 도착한 마지막 사람이 계단을 이용했으면
                cnt += s_time[t]+1;
                break;
            }
            cnt++;
        }
        answer = max(answer,cnt);
    }
    result = min(result, answer);
}
 
void dfs(int idx) {
    if (use[0].size() + use[1].size() == person.size()) {
        cal();
        return;
    }
    
    for (int i = idx; i < person.size(); i++) {
        for (int j = 0; j < 2; j++) {
            use[j].push_back(i);
            dfs(i + 1);
            use[j].pop_back();
        }
    }
}
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        result = INF;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = 0;
                scanf("%d", &temp);
                if (temp == 1) {//사람
                    person.push_back({ i,j });
                }
                else if (temp > 1) {
                    if (s_time[0] == 0) {
                        s_time[0] = temp;
                        stair1 = { i,j };
                    } 
                    else {
                        s_time[1] = temp;
                        stair2 = { i,j };
                    }
                }
            }
        }
        dfs(0);
        person.clear();
        printf("#%d %d\n", test_case, result);
        memset(s_time, 0, sizeof(s_time));
    }
}

++ 혹시 더 쉽게 풀 수 있는 방법이 없을까 싶어 다른 분의 코드를 봤는데

나처럼 계단마다 따로 3개의 공간을 두는 것이 아니라, 케이스를 나눠서 공식을 가지고 푸셨다.

case 1) 각 계단을 이용하는 사용자가 3명 이하, case 2) 그 외로 분류해서 

3명 이하라면 3개에 공간을 경쟁하지 않고 올 때마다 계단을 이용할수 있으니깐

마지막으로 끝나는 시간  = 마지막 사용자 도착시간(이동시간 + 대기시간(1))+ 계단 내려가는 시간

3명 초과라면, 3개의 공간 중 공간이 빌 때만 사용자가 이용할 수 있으니깐

마지막으로 끝나는 시간 = MAX(마지막 사용자 도착시간 + 계단 내려가는 시간 ,

  마지막 사용자에게 공간을 줄 사용자가 끝나는 시간(그 사용자의 도착시간 + 계단내려가는 시간) + 마지막 사용자가 내려가는 시간)

  마지막 사용자에게 공간을 줄 사용자는 마지막 사용자보다 3번째 전에 계단을 이용한 사용자

내 원래코드에서 이 공식을 이용한 코드는 아래와 같다

코드2)

#include <stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
 
#define INF 999999999
 
int n;
int s_time[2]; //계단 내려가는 시간 저장
pair<int, int> stair1, stair2; //계단 위치 저장
vector <pair<int, int>> person; //사람 위치 저장
vector <int> use[2]; //계단을 이용하는 사용자 저장. use[0] = 첫번째 계단을 이용하는 사람의 인덱스들
int result;
 
void cal() {
    int answer = 0;//최종시간
    vector <int> time[2];
 
    //계단 1 입구까지의 이동시간 + 1초 대기시간
    for (int i = 0; i < use[0].size(); i++) {
        int tmp= abs(person[use[0][i]].first - stair1.first) + abs(person[use[0][i]].second - stair1.second) + 1;
        time[0].push_back(tmp);
    }
    //계단 2 입구까지의 이동시간 + 1초 대기시간
    for (int i = 0; i < use[1].size(); i++) {
        int tmp = abs(person[use[1][i]].first - stair2.first) + abs(person[use[1][i]].second - stair2.second) + 1;
        time[1].push_back(tmp);
    }
    sort(time[0].begin(), time[0].end());
    sort(time[1].begin(), time[1].end());
    //각 계단을 완료하는 시간
    for (int t = 0; t < 2; t++) {
        if (time[t].size() == 0) continue;
        int cnt = 0;
        int idx = time[t].size() - 1;//가장 마지막으로 도착하는 사람 인덱스
        if (time[t].size() > 3) {//3명초과면
            // 가장 마지막 사람 도착시간 + 계단내려가는 시간 또는 가장 마지막 사람에게 자리를 줄 사람이 끝나는 시간 + 계단내려가는 시간
            cnt = max(time[t][time[t].size() - 1] + s_time[t], time[t][idx - 3] + s_time[t] * 2);
        }
        else {//3명이하면, 마지막 사람 도착하자마자 계단 이용가능 -> 마지막도착시간 + 계단내려가는 시간
            cnt = time[t][idx] + s_time[t];
        }
        answer = max(answer,cnt);
    }
    result = min(result, answer);
}
 
void dfs(int idx) {
    if (use[0].size() + use[1].size() == person.size()) {
        cal();
        return;
    }
    
    for (int i = idx; i < person.size(); i++) {
        for (int j = 0; j < 2; j++) {
            use[j].push_back(i);
            dfs(i + 1);
            use[j].pop_back();
        }
    }
}
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        result = INF;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = 0;
                scanf("%d", &temp);
                if (temp == 1) {//사람
                    person.push_back({ i,j });
                }
                else if (temp > 1) {
                    if (s_time[0] == 0) {
                        s_time[0] = temp;
                        stair1 = { i,j };
                    } 
                    else {
                        s_time[1] = temp;
                        stair2 = { i,j };
                    }
                }
            }
        }
        dfs(0);
        person.clear();
        printf("#%d %d\n", test_case, result);
        memset(s_time, 0, sizeof(s_time));
    }
}