[모의 SW 역량테스트] 2383. 점심 식사시간

[모의 SW 역량테스트] 점심 식사시간

---

1. 이해하기

• 이동 완료 시간은 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간이다.

• 사람들이 아래층으로 이동하는 시간은 계단 입구까지 이동 시간과 계단을 내려가는 시간이 포함된다.

• 계단 입구까지 이동 시간: |PR-SR|+|PC-SC|

  (PR,PC: 사람 P의 세로,가로위치, SR,SC: 계단 입구 S의 세로,가로위치)

• 계단을 내려가는 시간

  • 계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다.
  • 계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다.
  • 이미 계단을 3명이 내려가고 있는 경우, 그 중 한명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기한다.
  • 계단마다 길이 K가 주어지며, 계단을 완전히 내려가는데 K분이 걸린다.

• 모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾는 문제.

• 모든 사람들을 모든 계단에 대해서 구해보는 완전탐색 문제.

---

2. 구현하기

• 계단 입구까지 이동 시간

  int abs(int a) {
      return (a<0)?-a:a;
  }
  
  int get_dist(int x, int y, int x1, int y1) {
      return abs(x-x1)+abs(y-y1);
  }

• 계단을 내려가는 시간

  • 이 때, 각 사람들이 선택한 계단에 도착하는 시간을 이용한다.
  • 계단에 도착했을 때, 계단이 비어있는 경우 계단의 길이를 넣어주고 기다리고 있던 경우에는 길이-1을 넣어준다. 기다리고 있던 경우는 계단이 비자마자 내려가기 때문이다.

  int get_finish_time(vector<int> chosen, int stair_num) {
      memset(in_stair,-1,sizeof(in_stair));
      int time = 0;
      int size = chosen.size();
      int idx = 0;
      sort(chosen.begin(),chosen.end());
      while(idx < size) {
          time++;
          for(int i = 0; i < 3; i++) {
              if(in_stair[i] >= 0) in_stair[i]--;
          }
          while(chosen[idx] <= time) {
              bool flag = false;
              for(int i = 0; i < 3; i++) {
                  if(in_stair[i] == -1) {
                      flag = true;
                      if(chosen[idx] < time) {
                          in_stair[i] = stair_len[stair_num]-1;
                      } else in_stair[i] = stair_len[stair_num];
                      idx++;
                      break;
                  }
              }
              if(!flag) break;
          }
      }
      while(1) {
          bool flag = false;
          for(int i = 0; i < 3; i++) {
              if(in_stair[i] >= 0) {
                  flag = true;
                  in_stair[i]--;
              }
          }
          if(!flag) break;
          time++;
      }
      return time;
  }

• 모든 사람마다 계단을 선택하게 한 후, 선택에 따른 걸리는 시간을 구하고 최솟값을 찾는다.

  int solve(int index, vector<int> first, vector<int> second) {
      int size = person.size();
      if(size == index) {
          int f = get_finish_time(first,0);
          int s = get_finish_time(second,1);
          return max(f,s);
      }
  
      int ret = MAX;
      int f_d = get_dist(person[index].x, person[index].y, stair[0].x, stair[0].y);
      first.push_back(f_d);
      ret = min(ret,solve(index+1,first,second));
      first.pop_back();
      int s_d = get_dist(person[index].x, person[index].y, stair[1].x, stair[1].y);
      second.push_back(s_d);
      ret = min(ret,solve(index+1,first,second));
      second.pop_back();
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
struct Point{
    int x,y;
};
const int MAX = 987654321;
int map[10][10];
vector<Point> person;
vector<Point> stair;
vector<int> stair_len;
int in_stair[3];
int N;

int abs(int a) {
    return (a<0)?-a:a;
}

int get_dist(int x, int y, int x1, int y1) {
    return abs(x-x1)+abs(y-y1);
}

int get_finish_time(vector<int> chosen, int stair_num) {
    memset(in_stair,-1,sizeof(in_stair));
    int time = 0;
    int size = chosen.size();
    int idx = 0;
    sort(chosen.begin(),chosen.end());
    while(idx < size) {
        time++;
        for(int i = 0; i < 3; i++) {
            if(in_stair[i] >= 0) in_stair[i]--;
        }
        while(chosen[idx] <= time) {
            bool flag = false;
            for(int i = 0; i < 3; i++) {
                if(in_stair[i] == -1) {
                    flag = true;
                    if(chosen[idx] < time) {
                        in_stair[i] = stair_len[stair_num]-1;
                    } else in_stair[i] = stair_len[stair_num];
                    idx++;
                    break;
                }
            }
            if(!flag) break;
        }
    }
    while(1) {
        bool flag = false;
        for(int i = 0; i < 3; i++) {
            if(in_stair[i] >= 0) {
                flag = true;
                in_stair[i]--;
            }
        }
        if(!flag) break;
        time++;
    }
    return time;
}

int solve(int index, vector<int> first, vector<int> second) {
    int size = person.size();
    if(size == index) {
        int f = get_finish_time(first,0);
        int s = get_finish_time(second,1);
        return max(f,s);
    }

    int ret = MAX;
    int f_d = get_dist(person[index].x, person[index].y, stair[0].x, stair[0].y);
    first.push_back(f_d);
    ret = min(ret,solve(index+1,first,second));
    first.pop_back();
    int s_d = get_dist(person[index].x, person[index].y, stair[1].x, stair[1].y);
    second.push_back(s_d);
    ret = min(ret,solve(index+1,first,second));
    second.pop_back();
    return ret;
}

void input() {
    stair.clear();
    stair_len.clear();
    person.clear();
    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) person.push_back({i,j});
            else if(2 <= map[i][j] and map[i][j] <= 10) {
                stair.push_back({i,j});
                stair_len.push_back(map[i][j]);
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        vector<int> first, second;
        cout << '#' << t << ' ' << solve(0,first,second) << '\n';
    }
    return 0;
}