[ SWEA 2383 ] 점심 식사시간 (C++) (2)

SWExpertAcademy의 점심 식사시간(2383)이다.

[ 문제풀이 ]

1) 지난 글에서는 점심식사시간을 정말 매초마다 일어나는 일들을 하나하나씩 처리하는 방법으로 구현해 보았다.

   이번 글에서는 보다 간단한 방법으로 해결해 보려고 한다.

   중복순열을 이용해서 계단을 선택하는 과정까지는 똑같으니 지난 글을 아직 읽고 오지 않았다면 읽고 와보도록 하자.

   [ 점심식사시간(2383) 풀이(1) ]

   이 풀이는 사람을 한명 한명 옮겨볼 것이 아니라, 각 계단의 마지막으로 계단을 이용하는 사람의 시간만 알 수 있다면

   정답을 구할 수 있을 것 같다 라는 생각에서 나온 풀이이다.

   만약에 6명의 사람이 있고, 1번계단을 3명, 2번계단을 3명이 이용하는 경우를 예로 들어보자.

   1번계단의 길이는 2, 2번계단의 길이는 3이라고 가정해보자.

   이 때, 1번 계단에 마지막으로 들어오는 사람이 5초에 들어오게 되고, 2번 계단에 마지막으로 들어오는 사람이 6초에

   들어오게 된다면 걸리는 시간이 얼마일까 ??

   바로 9초라는 것을 알 수 있다. 6초에 2번 계단으로 들어간 사람이 3초동안 내려오면 9초가 되기 때문이다.

   ( 물론, 이전 글에서 말했듯이, 들어오는 시간이라는 것은 대기시간을 포함해서 계산한 시간을 의미합니다. )

   우리는 여기서 6명이 모두 계단을 내려오는 시간을 알 필요가 없다는 것을 알 수 있다.

   각 계단에 마지막으로 들어오는 사람의 시간만 계단한다면 정답을 구할 수 있음을 알 수 있다.

   그러면 지금부터는 마지막 사람이 몇초에 계단에 들어갈 수 있는지를 구하는 방법과, 정답을 구하는 과정에서

   비교 및 신경 써줘야 할 부분에 대해서 알아보도록 하자.

  

2) 계단은 최대 사용자수가 3명이다. 즉, 누군가 계단에 가더라도 이미 3명이 사용하고 있다면 대기를 해줘야 한다.

   그럼 간단한 예시로 생각해보자.

   계단을 이용하려는 사람이 총 5명이고, 그 5명이 계단에 도착하는 시간이 빠른 순으로 {A, B, C, D, E } 라고 했을 때,

   이 때 마지막 으로 계단에 들어가는 사람이 몇초 인지를 구해보자.

   쉽게 이야기해서 'A'라는 사람이 계단에 1등으로 도착하고, 'B'라는 사람이 2등 ... 'E'가 5등으로 도착하는 상황이다.

   그렇다면 우리는 'E'가 계단을 이용할 수 있는 시간만 구하면 된다. 이용을 시작하는 시간을 구하면 자연스럽게

   이용을 종료하는 시간까지 알 수 있기 때문이다.

   그럼 딱 봤을 때, 'E'는 누가 계단 이용을 끝내야 계단에 들어갈 수 있을까 ?? 바로 'B'이다. 왜 ??

   처음에 'A'가 도착. 아무도 없으므로 바로 이용시작.

   두번째로 'B'가 도착. 1명이 이용하고 있으므로 바로 이용 시작.

   세번째로 'C'가 도착. 2명이 이용하고 있으므로 바로 이용 시작.

   네번째로 'D'가 도착. 3명이 이용하고 있으므로 대기.

   다섯번째로 'E'가 도착. 3명이 이용하고 있으므로 대기.

   어느 순간 'A'가 이용을 끝냄. → 대기하고 있던 'D'가 계단 이용 시작.

   어느 순간, 'B'가 이용을 끝냄. → 대기하고 있던 'E'가 계단 이용 시작.

   이기 때문에 'E'가 계단을 이용을 시작하는 시간은 'B'가 계단 이용을 끝내는 시간이다.

   그럼 상황을 바꿔서, 계단을 이용하려는 사람이 2명일 경우는 어떻게 해줘야 할까 ?

   위와 같은 계산을 할 필요가 없다. 가장 마지막에 계단에 도착하는 사람이 언제 도착하든지 무조건 계단을 바로 이용할 수

   있기 때문에, 계단 이용자수가 3명 이상인 경우가 없기 때문에 바로 구해버리면 된다.

   그럼 이제부터 위의 과정을 한번 구해보자.

   먼저, 계단과 사람 사이의 거리를 구해서 Vector에 저장을 해주었다.

   물론, 계단에 2개이기 때문에 vector를 2칸짜리 벡터배열로 만들어 주었고, 각 계단을 이용하려는 사람들의 거리를

   구해서 저장해주었다.

   이 후, 이 vector를 오름차순으로 정렬을 해주었다. 그렇게되면 ?? 자연스럽게 계단을 가장 빨리 이용할 수 있는 사람부터

   가장 마지막에 이용하는 사람 순으로 vector의 값이 정렬될 것이다.

   그리고 크게 2가지 경우로 나눌 수가 있다.

   1. 벡터의 크기가 3 이하인 경우

   2. 벡터의 크기가 4 이상인 경우

   1. 벡터의 크기가 3이하이다 라는 것이 의미하는 것이 뭘까 ? 바로 해당 계단을 이용하려는 사람의 수가 3명 이하라는

     것이다. 그렇게되면 ? 계단이 꽉 차서 이용하지 못하는 경우가 발생하지 않는다는 것이다.

     따라서, 이 경우 계단을 모두 이용하는데 걸리는 시간은

     "가장 마지막에 계단 이용을 시작하는 사람의 시간 + 계단의 길이" 가 된다.

     그런데 가장 마지막에 계단 이용을 시작하는 사람의 시간은 ? 벡터의 가장 마지막 원소가 된다.

     오름차순으로 정렬을 했기 때문에, 가장 마지막 원소는 가장 마지막에 계단에 도착하는 사람의 시간을 의미하므로

     이 시간 + 계단의 길이를 한 것이 해당 계단을 이용하는 최종 시간이 된다.

   2. 두 번째는 벡터의 크기가 4 이상인 경우이다.

      이 경우, 대기하는 시간이 발생할 수 있다. 즉, 마지막 사람이 계단에 도착했을 때, 앞에 있는 누군가가 빠져야만

      계단을 이용할 수 있는 경우가 발생할 수 있다는 말이다.

      그 누군가를 구하는 방법을 우리는 위에서 간략하게 알아보고 왔다.

      그럼 그 방법을 보다 구체적으로 어떻게 접근해야 하는지 예시를 통해서 알아보자.

      벡터를 정렬해 봤더니 { 1, 2, 3, 4, 5 } 가 들어있었다고 가정해보자. 계단의 길이는 5이다.

      다시한번 정리하자면 벡터에 저장되어있는 { 1, 2, 3, 4, 5 } 가 의미하는 것은, 가장 첫번째로 계단에 도착하는

      사람이 걸리는 시간 = 1초, 2등으로 도착하는 사람 = 2초, 5등으로 도착하는 사람 = 5초 라는 것이다.

      그럼 이때, 가장 마지막(5초에)에 도착하는 사람이 계단 이용을 시작할 수 있는 시간을 구해보자.

      위에서도 말했듯이, 5초에 도착하는 사람이 계단을 이용하기 위해서는 '2'초에 도착한 사람이 계단 이용을 끝내는

      시간에 이용을 시작할 수 있다.

      그럼 인덱스 적으로 접근해보겠다.

      V[0] = 1, V[1] = 2, V[2] = 3, V[3] = 4, V[4] = 5 가 된다.

      가장 마지막에 도착하는 사람의 인덱스 번호는 '4'이다. '4'가 이용을 시작하기 위해서는 '1'번 인덱스번호인

      사람이 이용을 끝내야 하는 것이다.

      즉, 마지막 사람의 인덱스번호 - 3 의 인덱스 번호를 갖는 사람이 이용을 끝내야 한다는 것이다. 그럼 이 공식이

      항상 성립되는지 확인해보자.

      사람이 7명 있는 경우

      - 공식에 의하면.. 마지막 사람의 인덱스 번호 = 6 , 6 - 3 = 3. 인덱스 3번인 사람이 계단 이용을 끝내야 한다.

        인덱스번호 : 0, 1, 2, 3, 4, 5, 6

        0 번 사용시작

        1 번 사용시작

        2 번 사용시작

        3, 4, 5, 6번 = 이미 3명이므로 대기

        어느 순간 0번 계단이용 완료 → 3번 계단이용 시작

        어느 순간 1번 계단이용 완료 → 4번 계단이용 시작

        어느 순간 2번 계단이용 완료 → 5번 계단이용 시작

        어느 순간 3번 계단이용 완료 → 6번 계단이용 시작

        어느 경우에도 위의 식이 성립을 할 수가 있다.

      하지만 이렇게 답을 도출하면 틀리게 된다. 생각을 해줘야 할 상황이 하나 더있다.

      이런 경우를 생각해보자. 4명의 사람이 계단을 이용하는데, 계단에 도착하는 1등 ~ 3등 사람은 1초만에 계단에 도착해서

      계단을 이용한다. 계단의 길이는 1이다. 그런데, 4등 즉, 마지막으로 도착하는 사람이 100초 후에 계단에 도착하게 된다.

      이런 경우이다.

      이 때도, 위의 공식처럼 인덱스 번호로는 3 이고, 3 - 3 = 0 이니까 0번 사람이 끝나는 시간에 계단 사용을 시작하니까

      1(0번 사람이 계단에 도착하는시간) + 1(0번 사람이 계단을 내려가는시간) = 2.

      2초에 계단 이용을 시작하니까 최종시간은 3 !

      딱 봐도 말도 안되는 경우이다. 그래서 우리는 2개의 값을 비교를 해줄 필요가 있다.

      1. 공식 처럼 계산 했을 때 나오는 시간

      2. 공식을 사용하지 않고, 그냥 마지막 사람이 도착한 시간 + 계단의 길이

       2개의 값 중에서 더 큰 값이 "가장 마지막에 계단 사용을 위해서 도착한 시간" 이 된다.    

     

      말로 풀이를 하다보니 이해가 잘 되지 않는 부분이 있을수도 있는데, 코드를 보면서 천천히 읽어보면 충분히 이해할 수

      있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
struct STAIR
{
    int x;
    int y;
    int Len;
    int Num;
};
 
struct PERSON
{
    int x;
    int y;
    int MoveTime;
    int StartTime;
    int EndTime;
    bool Finish;
};
 
int N, P_Num, Answer;
int MAP[MAX][MAX], Select[MAX];
PERSON Person[MAX];
STAIR Stair[2];
 
int Min(int A, int B) { if (A < B) return A; return B; }
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 987654321;
}
 
void Input()
{
    int P_Idx, Idx;
    P_Idx = Idx = 0;
 
    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[P_Idx].x = i;
                Person[P_Idx].y = j;
                Person[P_Idx].MoveTime = Person[P_Idx].StartTime = Person[P_Idx].EndTime = -1;
                Person[P_Idx].Finish = false;
                P_Idx++;
            }
            else if (MAP[i][j] >= 2)
            {
                Stair[Idx].x = i;
                Stair[Idx].y = j;
                Stair[Idx].Len = MAP[i][j];
                Stair[Idx].Num = 0;
                Idx++;
            }
        }
    }
    P_Num = P_Idx;
}
 
int Dist(int P_Idx, int S_Idx)
{
    int dx = abs(Person[P_Idx].x - Stair[S_Idx].x);
    int dy = abs(Person[P_Idx].y - Stair[S_Idx].y);
 
    return (dx + dy) + 1;
}
 
void Func()
{
    int Time[2] = { 0, 0 };            // 가장 마지막 사람이 계단에 도착하는데 걸리는 시간을 저장.
    vector<int> V[2];                // 계단에 도착하는데 걸리는 시간을 저장하는 Vector.
    for (int i = 0; i < P_Num; i++)
    {
        int Idx = Select[i];
        Person[i].MoveTime = Dist(i, Idx);
        V[Idx].push_back(Person[i].MoveTime);    // 거리를 구해서, 해당 계단 벡터에 push.
    }
 
    for (int i = 0; i < 2; i++)
    {
        if (V[i].size() == 0) continue;
        sort(V[i].begin(), V[i].end());            // 오름차순으로 정렬.
        Time[i] = V[i][V[i].size() - 1];        // 가장 마지막으로 도착하는 사람의 시간 저장.
 
        if (V[i].size() > 3)                    // 대기열이 존재하는 경우
        {
            int Idx = V[i].size() - 1;            // 가장 마지막으로 도착하는 사람의 Index
            int Temp = Idx - 3;                    // 공식 : Index - 3.
 
            Time[i] = Bigger(Time[i] + Stair[i].Len, V[i][Temp] + Stair[i].Len + Stair[i].Len);
            /* 
               여기서 2개의 값 비교.
               1. 공식을 사용하지 않고, 가장 마지막에 도착한 사람의 시간 + 계단의 길이
               2. 공식을 사용해서 나오는, -3한 Index번호를 가진 사람이 계단 이용을 끝내는 시간 + 계단의 길이 
            */
        }
        else Time[i] = Time[i] + Stair[i].Len;
        // 계단 이용자 수가 3명 이하라면, 그런건 상관없이 그냥 마지막에 도착하는 사람의 시간 + 계단의 길이
    }
 
    int MaxTime = Bigger(Time[0], Time[1]);
    // 최종 시간은, 2개의 계단 중에서 더 시간이 오래걸리는 계단의 시간.
    Answer = Min(Answer, MaxTime);
    
}
 
void DFS(int Cnt)
{
    if (Cnt == P_Num)
    {
        Func();
        return;
    }
 
    for (int i = 0; i < 2; i++)
    {
        Select[Cnt] = i;
        DFS(Cnt + 1);
    }
}
 
void Solution()
{
    DFS(0);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}