ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2383.점심 식사시간
    알고리즘/SW Expert Academy 2020. 7. 10. 01:09

    이번에 풀어볼 문제는 SW Expert의 2383 점심식사시간이다.

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    어떻게 풀지는 알겠는데 구현과 설계가 생각보다 많이 어려운 문제이다.

    이전에 풀어봤던 2477 자동차 정비소와 비슷한 난이도처럼 느껴졌지만 더 어려웠던거 같다.

    딱 보면 이렇게 풀면 되는데.. 라는 생각은 드는데 구현이 굉장히 복잡했고 결국 시간안에 풀지 못해서

    다른사람의 코드를 공부하는 식으로 진행했다.. 나중에 다시한번 풀어봐야겠다.. ㅠㅠ

    참고 블로그 : https://charm-charm.postype.com/post/3602958

     

     


     

    이 문제의 포인트는 다음과 같다.

    1. 사람들이 선택할 수 있는 모든 계단의 경우의 수를 다 진행해야한다

      => 조합 => 재귀함수이용 

     

    2. 대기열에 어떤식으로 값을 저장할 것이고 어떤식으로 소요시간의 진행도를 구현할 수 있는지

      => 설계 능력과 개인의 역량이다..

     

     


     

    < Code 설명 >

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <deque>
    #include <algorithm>
    #include <string.h>
     
    #define MAX 11
     
    using namespace std;
     
    int T, N;
    int map[MAX][MAX]; // 맵 저장 변수
    int choice[MAX]; // 계단 종류(1번, 2번) 선택
     
    deque<pair<intint>>stair; // 계단 좌표
    deque<pair<intint>>person;// 사람 좌표
     
    int person_cnt; // 사람 수
    int ans; // 정답 (최단시간)
     
    int search(){
        int time[MAX]; // 이동시간 저장 변수 (계단 입구까지 이동에 걸린시간)
        int t = 0;   // 시간의 흐름 변수
        int cnt = 0// 이동이 완료된 사람 카운트 변수
        deque<int>wait[2]; // 2가지 종류의 계단 입구 대기열
     
        for (int i = 0; i < person_cnt; i++){ // 사람들의 계단까지의 거리 계산
            //계단의 경우 이전 johap 함수에서 선택한 계단과 사람의 거리로 계산함
            time[i] = abs(person[i].first - stair[choice[i]].first) + abs(person[i].second - stair[choice[i]].second);
        }
     
        while (true){
            if (t >= ans) // 흐른 시간이 최소시간보다 크면 굳이 계산할 필요가 없으므로
                return t; // 현재까지의 시간 그냥 리턴
            if (cnt == person_cnt) // 사람 인원수 만큼 전부 이동이 끝났다면 종료
                return t; // 총 걸린 시간 리턴
     
            for (int i = 0; i < 2; i++){ // 계단을 타기 시작하면
                int wait_size = wait[i].size();
                for (int j = 0; j < wait_size; j++){ // 계단 입구에서 기다리는 사람 수 만큼 탐색
                    int first = wait[i].front(); // 계단입구에 제일 먼저 서있는 사람의 대기 시간을 저장
                    wait[i].pop_front(); // 해당 값을 대기열에서 제거
                    first -= 1// 대기시간 1초 감소
                    if (first != 0// 시간이 지났지만 0초가 아닌경우
                        wait[i].push_back(first); // 해당 값을 다시 대기열에 저장
                    else if (first == 0// 계단을 타는 소요시간 다 끝났다면
                        cnt += 1// 이동이 완료된 사람 카운트
                }
            }
     
            for (int i = 0; i < person_cnt; i++){ // 계단 입구에 도착하면
    // 계단 입구에 오는 사람들은 전부다 push하고 3명보다 작거나 클때로 나눠서 예외처리 하는 것이 point!
                if (t == time[i]){// 이동거리와 걸린시간이 같을 때
                    if (wait[choice[i]].size() < 3){ // 해당 사람이 선택한 계단입구의 대기 인원이 3명보다 적다면
                        wait[choice[i]].push_back(map[stair[choice[i]].first][stair[choice[i]].second]); // 대기열에 해당 계단을 탔을 때 걸리는 시간을 저장
                    }
                    else //대기 인원이 꽉찬 경우
                        // 역시나 대기열에 해당 계단이 걸리는 시간을 넣되, 제일 먼저 계단을 타는 녀석의 계단의 소요시간을 더해줘서 대기시간을 늘려줌
    // 제일 첫 번째 녀석이 제일 먼저 내려갈 것이고 그 이후에 자리가 빌 것이기 때문이다.
                        wait[choice[i]].push_back(map[stair[choice[i]].first][stair[choice[i]].second] + wait[choice[i]].front()); 
                }
     
            }
            t++// 시간의 흐름 +1
        }
    }
     
    void johap(int cnt){
        // 재귀함수 반환 조건 : 사람수 만큼 검색 완료되었다면 최소시간 계산 후 반환
        if (cnt == person_cnt){ // 사람 수 만큼 검색했다면
            int tmp = search(); // 탐색 후 걸린 시간 저장
            ans = min(tmp, ans); // 최소 시간 저장
            return;
        }
        // 실질적인 조합 진행 재귀함수
        choice[cnt] = 0// 1번 계단을 고른경우
        johap(cnt + 1);  // 다음 계단 선택을 위해 사람수 +1
        choice[cnt] = 1// 2번 계단을 고른 경우
        johap(cnt + 1); // 다음 계단 선택을 위해 사람수 +1
    }
     
    void init(){
        memset(map, 0sizeof(map));
        stair.clear();
        person.clear();
    }
     
    int main(){
        freopen("2383.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            init();
            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// 계단 좌표 저장
                        stair.push_back(make_pair(i, j));
                    else if (map[i][j] == 1// 사람 좌표 저장
                        person.push_back(make_pair(i, j));
                }
            }
            person_cnt = person.size(); // 계단을 타는 사람들의 크기 변수
            ans = 987654321// 정답변수
            johap(0); // 계단입구와 사람들간의 조합 시작 ( 모든 경우의 수 조합으로 체크 )
            cout << "#" << z << " " << ans << "\n";
        }
        return 0;
    }
    cs
    반응형

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    1952.수영장  (0) 2020.07.23
    2382.미생물격리  (0) 2020.07.21
    2477.차량 정비소  (2) 2020.07.07
    2105.디저트 카페  (0) 2020.06.27
    2115.벌꿀채취  (0) 2020.06.23

    댓글

Designed by Tistory.