[SW Expert] 2383 점심 식사시간

문제보기

두단계로 나눠서 풀이했다.

1.dfs로 사람들이 1번 계단으로 갈지 2번 계단으로 갈지 결정하는 모든 경우의 수를 도출

2. 도출된 경우의 수로 cur변수를 1씩 증가시키며 계단에 도착하는지 검사

-계단에 도착시 계단 높이 + 1을 계단 벡터(stairPool)에 push (계단에 도착 후 1분뒤 내려가기 시작하므로)

-계단에 사람이 있다면 한칸씩 내려감

-모든 사람이 내려갈때까지 반복

처음에 50개의 테스트 케이스 중 49개의 테스트 케이스만 맞아서 답답했다.

아마도 계단에 내려가는 사람이 3명으로 꽉 차서 대기하는 사람이 있을 때,

어떤 사람이 계단 내려가기를 완료한 시점에서 대기하던 사람이 바로 내려갈 수 있어야하는데 그부분을 처리하지 못해서 그런것같다.

---

#include <vector>

#include <iostream>

#include <queue>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

int map[11][11];

int N, M;

int ans = 99999;

int stairNum[11];

typedef struct door {

    int x;

    int y;

    int h;

}door;

vector<pair<int, int> > p;

vector<door> s;

void calc() {

    pair<int,int> remainDis[11] = {};

int stairIdx[2] = {};

vector<int> stairPool[2];

    for (int i = 0; i<M; i++) {

//거리계산

        remainDis[i].first = fabs(s[stairNum[i]].x - p[i].first) + fabs(s[stairNum[i]].y - p[i].second);

remainDis[i].second = stairNum[i];

}

sort(remainDis,remainDis+M);

int cur = 1;

    int cnt = 0;

    for(cur = 1;cur <= 20; cur++) {

if(cnt == M) {

    ans = min(ans, cur-1);

return;

}

//계단별 계산

        for (int i = 0; i<2; i++) {

if(stairPool[i].size() > 0){

for (int j = stairIdx[i]; j< stairIdx[i] + 3; j++) {

if( j >= stairPool[i].size()) break;

if(stairPool[i][j] > 0){

//한칸씩 내려감

stairPool[i][j]--;

}

if(stairPool[i][j] == 0){

//계단 다 내려오면 카운트

stairIdx[i]++;

cnt++;

}

}

}

        }

        for (int i = 0; i<M; i++) {

//계단에 도착할 시간

if(cur == remainDis[i].first){

int sn = remainDis[i].second;

//계단 높이 + 내려가는거 대기시간(1)

stairPool[sn].push_back(s[sn].h+1);

}

        }

    }

}

void dfs(int depth) {

    if (depth == M) {

        calc();

    }

    else {

        for (int i = 0; i<2; i++) {

            stairNum[depth] = i;

            dfs(depth + 1);

        }

    }

}

int main() {

    freopen("input.txt", "r", stdin);

    int T;

    scanf("%d", &T);

    for (int t = 1; t <= T; t++) {

        int doorNum = 0;

        scanf("%d", &N);

        for (int i = 0; i<N; i++) {

            for (int j = 0; j<N; j++) {

                scanf("%d", &map[i][j]);

                if (map[i][j] == 1) p.push_back(make_pair(i, j));

                else if (map[i][j] > 0) {

                    door dr;

                    dr.x = i;

                    dr.y = j;

                    dr.h = map[i][j];

                    //dr.wait = 0;

                    //memset(dr.pool, 0, sizeof(dr.pool));

                    s.push_back(dr);

                }

            }

        }

        M = p.size();

        dfs(0);

        printf("#%d %d\n", t, ans);

        p.clear();

        s.clear();

        ans = 99999;

    }

}