2383번 점심 식사시간

엄청 어려운 문제였다.(내가 못 하는건 비밀)

아마 며칠 동안 풀어도 못 풀었을 것이다.

어쩔 수 없이 강의들으면서 코드를 작성하였다.

이 문제를 통해 기억해야할 것

1. 문제를 풀기 전에 설계를 잘 하자.

2. 배열을 잘 활용하자

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
#define Max_people 11
#define Max_time Max_people * 2 + Max_people*Max_people
// Max_time : 최대 도착 시간 = 최대 도착 시간인 Max_people * 2 + 길이가 Max_people인 하나의 계단을
// Max_people명이 모두 다 내려갈 때
 
using namespace std;
 
int N = 0;
int people_count = 0;
int stair_count = 0;
int match[Max_people] = { 0, }; // match[h]=s : h번 째 사람이 s번 째 계단을 이용(h>=1)
int ans = 987654321;
int building[Max_people][Max_people] = { 0, };
 
vector<pair<int, int> > people[Max_people];
vector<pair<int, int> > stair[2]; // 계단은 무조건 2개
 
void init() // 초기화
{
    ans = 987654321;
 
    people_count = 0;
 
    stair_count = 0;
 
    for (int p = 0; p < 11; p++)
    {
        if (!people[p].empty()) people[p].clear();
    }
 
    for (int s = 0; s < 2; s++)
    {
        if (!stair[s].empty()) stair[s].clear();
    }
}
 
int dist(int human_index, int stair_index)
{
    int dy = abs(people[human_index].front().first - stair[stair_index].front().first);
    int dx = abs(people[human_index].front().second - stair[stair_index].front().second);
 
    return dy + dx;
}
 
void update()
{
    int total_time = 0;
 
    // 두 계단은 각각 독립적(서로 영향 X)
    for (int stair_index = 0; stair_index < 2; stair_index++)
    {
        int arrive_time[Max_people * 2] = { 0, };
        // arrive_time[time] : 시간이 time일 때, 계단에 도착한 사람의 수
        // 최대 걸리는 시간은 (1, 1)에서 (N, N)으로 올 때 이다. 즉, 2N이다.
 
        int current_stair[Max_time] = { 0, };
        // current_stair[time] : 시간이 time일 때, 그 계단을 내려가고 있는 사람의 수
 
        for (int human_index = 0; human_index < people_count; human_index++)
        {
            if (match[human_index] == stair_index)
            {
                arrive_time[dist(human_index, stair_index) + 1]++;
                // + 1을 해준 이유는 어차피 계단을 도착하고 나서, 1분 후에 계단을 내려갈 수 있기 때문이다.
            }
        }
 
        // stair_index번 째 계단을 내려가는 사람이 모두 작업을 마치기 위해 필요한 최소 시간
        int now_min_time = 0;
 
        // 계단에 도착한 시간(time)을 기준으로 순차적으로 오름차순으로 각 사람이 계단을 내려가는 시뮬레이션
        // 최대 도착 시간이 20인 이유는 배열을 선언할 때, 최대 11이므로, 실제 계산은 (0, 0)을 계산하는 것이 아닌
        // (1, 1) ~ (11, 11)이기 때문에 |11-1| + |11-1| = 20이다.
        for (int time = 1; time <= 20; time++)
        {
            // 그 시간(=time)일 때, 계단에 도착하는 사람이 존재한다면
            while (arrive_time[time]--)
            {
                // 해당 계단을 내려가는데 필요한 시간(=그 해당 계단의 길이)
                int remain_time = building[stair[stair_index].front().first][stair[stair_index].front().second];
 
                for (int walk_time = time; walk_time < Max_time; walk_time++)
                {
                    // 햔재 walk_time(time)시간일 때, 계단을 내려가는 사람 수가 3명보다 적으면
                    if (current_stair[walk_time] < 3)
                    {
                        current_stair[walk_time]++; // 1명이 내려가고 있다는 것을 추가
 
                        --remain_time; // 그에 따라 계단을 1 내려갔으므로, 1 감소
 
                        if (remain_time == 0) // 계단을 내려갔다면
                        {
                            now_min_time = max(now_min_time, walk_time + 1);
 
                            // + 1을 해준 이유는
                            // 예를 들어, 계단 길이가 3이고, time이 5일 때, 현재 그 시간에 계단을 내려가는 사람 수가 3명보다 적을 때
                            // if문이 실행되고, 그 5분일 때 바로 remain_time이 1 감소한다.(remain_time = 2)
                            // 6분일 때, remain_time = 1
                            // 7분일 때, remain_time = 0
                            // remain_time이 0일 때, 바로 도착했다는 if문이 실행된다.
                            // 근데 +1을 안 해주면 그 시간대(time = 7)로 기록해버린다.
                            // 그래서 +1을 해주어야 '계단 길이 = 내려간 시간'임을 활용할 수 있다.
 
                            break;
                        }
                    }
                }
            }
 
            // 전체 계단을 내려가는데 필요한 최소의 시간 =
            // 두 계단을 내려가는데 필요한 최소의 시간 중에서 최댓값
            total_time = max(total_time, now_min_time);
        }
    }
 
    ans = min(ans, total_time);
}
 
void DFS(int human_index) // BackTracking
{
    if (human_index == people_count) // 결정했다면
    {
        update();
 
        return;
    }
 
    for (int stair_index = 0; stair_index < 2; stair_index++)
    {
        match[human_index] = stair_index; // 사람이 어느 계단을 탈지 결정
 
        //printf("%d번 째 사람이 %d번 째 계단 타는 경우의 수\n\n", human_index, stair_index);
        
        DFS(human_index + 1);
    }
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        init();
 
        scanf("%d", &N);
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                scanf("%d", &building[i][j]);
 
                if (building[i][j] == 1)
                {
                    people[people_count++].push_back({ i,j });
                }
                else if (building[i][j] >= 2)
                {
                    stair[stair_count++].push_back({ i,j });
                }
            }
        }
 
        DFS(0);
 
        printf("#%d %d\n", tc, ans);
    }
 
    return 0;
}