22.06.08. 풀었던 문제들

1. 추석 트래픽

생각보다 간단한 문제였음. 로그 갯수가 바뀌는 위치 : 각 로그의 시작점 또는 끝점이다. 또한 greedy하게 시작점은 탐색할 필요가 없는 게, 앞에서 이미 탐색되는 위치이기 때문(끝점 탐색하면서) 따라서 끝점만 탐색하면 된다. 끝점 기준으로 +1초 탐색하면 됨

​

​

2. 셔틀버스

시간이 작기 때문에 그냥 시뮬레이션 돌려도 된다. 시간 뒤에서부터 탐색, 탈 수 있으면 break, 못타면 계속 탐색.

탐색 시 crew의 대기시간이 버스도착시간보다 크면 bus index 증가, 그렇지 않으면 bus값에 1 빼줌. 그러고 만약 bus가 가득 차면 bus index++. 이 때, '나'의 시간이 crew 시간보다 작고 버스 도착시간보다 작다 -> 나는 버스에 탈 수 있다. (크루 도착시간이 오름차순)

// 셔틀버스

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

int stringToMinute(string s){
    return 60 * stoi(s.substr(0, 2)) + stoi(s.substr(3, 2));
}

string timeToString(int t){
    int hour = t/60;
    string shour;
    if(hour == 0){
        shour = "00";
    }
    else if(hour < 10){
        shour = "0" + to_string(hour);
    } else{
        shour = to_string(hour);
    }
    
    int minute = t%60;
    string sminute;
    if(minute == 0)
        sminute = "00";
    else if(minute < 10){
        sminute = "0" + to_string(minute);
    } else{
        sminute = to_string(minute);
    }
    
    return shour + ":" + sminute;
    
}

string solution(int n, int t, int m, vector<string> timetable) {
    vector<int> crews;
    int firstBusArriveTime = stringToMinute("09:00");
    int lastBusArriveTime = firstBusArriveTime + (n-1) * t;
    for(string s : timetable){
        int crewArriveTime = stringToMinute(s);
        if(crewArriveTime > lastBusArriveTime) continue;
        crews.push_back(crewArriveTime);
    }
    sort(crews.begin(), crews.end());
    
    for(int objectTime = lastBusArriveTime + 1; objectTime >= 0; objectTime--){
        bool flag = false;
        vector<int> bus(n, m);
        if(objectTime == 541){
            cout<<"CHECK"<<endl;
        }
        for(int ci = 0, bi = 0; ci < crews.size() && bi < n; ci++){
            int busArriveTime = firstBusArriveTime + t * bi;
            if(crews[ci] <= busArriveTime){
                if(crews[ci] > objectTime && objectTime <= busArriveTime){
                    flag = true;
                    break;
                } else{
                    bus[bi]--;
                }
            } else{
                ci--; bi++;
                if(bi >= n) break;
            }
            if(bus[bi] == 0){
                bi++;
            }
        }
        for(int bi = 0; bi < n; bi++){
            int busArriveTime = firstBusArriveTime + t * bi;
            if(objectTime <= busArriveTime && bus[bi] > 0){
                flag = true;
                break;
            }
        }
        if(flag) return timeToString(objectTime);
    }
    
    
    return timeToString(0);
}

 

3. 합승 택시 요금

처음엔 벨만-포드로 풀고 경로를 저장해서 풀려 했는데 벨만포드는 O(VE) 반면 플로이드-와샬은 O(V^3)이기 때문에 size 200 내에선 충분히 풀 수 있었다. 따라서 플로이드-와샬 사용

​

​

4. 퍼즐 조각 채우기

귀찮은 문제다. 짜야 하는 함수들만

table에서 모든 조각을 가져오는 함수

조각들을 90도 rotate시키는 함수

1의 개수를 count하는 함수

두 조각이 match인지 검사하는 함수

이렇게 짜야 한다.

이렇게 짜면 쉽게 구할 수 있는데, game_board와 table에서 조각들을 가져오고 이 조각들을 n * m으로 2중포문으로 돌리면 된다. 다만 돌릴 때 table_part는 회전가능하므로 회전한 것도 검사할 것. 만약 matching이라면 해당 조각을 table_parts에서 지운다.

약간 깔끔하게 잘 짠 것 같다.

// 자물쇠와 열쇠

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<vector<int>> rotate(vector<vector<int>> m){
    vector<vector<int>> a(m[0].size(), vector<int>(m.size()));
    
    for(int r = 0; r<a.size(); r++){
        for(int c= 0; c<a[0].size(); c++){
            a[r][c] = m[c][m[0].size()-1-r];
        }
    }
    return a;
}

bool isMatching(vector<vector<int>>& nlock, int sr, int sc, int num_slot, vector<vector<int>>& key){
    int nlocksize = nlock.size(), keysize = key.size();
    int cnt = 0;
    for(int r = 0; r < keysize; r++){
        for(int c = 0; c<keysize; c++){
            if(nlock[sr + r][sc + c] == 2) continue;
            if(nlock[sr + r][sc + c] == 1 && key[r][c] == 1) return false;
            if(nlock[sr + r][sc + c] == 0 && key[r][c] == 0) return false;
            if(nlock[sr + r][sc + c] == 0 && key[r][c] == 1) cnt++;
        }
    }
    return cnt == num_slot;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    // keysize <= locksize
    int keysize = key.size(), locksize = lock.size(), nlocksize = locksize + 2 * keysize - 2;
    vector<vector<int>> nlock(nlocksize, vector<int>(nlocksize, 2));
    int num_slot = 0;
    for(int r = 0; r<locksize; r++){
        for(int c = 0; c<locksize; c++){
            nlock[r + keysize-1][c + keysize-1] = lock[r][c];
            if(lock[r][c] == 0)num_slot++;
        }
    }
    
    vector<vector<vector<int>>> keys;
    keys.push_back(key);
    for(int i = 0; i<4; i++){
        keys.push_back(rotate(keys[keys.size()-1]));
    }
    
    
    for(int lr = 0; lr < nlocksize - keysize + 1; lr++){
        for(int lc = 0; lc < nlocksize - keysize + 1; lc++){
            for(int i = 0; i<4; i++){
                bool result = isMatching(nlock, lr, lc, num_slot, keys[i]);
                if(result) return true;
            }
        }
    }
    
    return false;
}
​