22.06.19. 풀었던 문제들

1. 몸짱 트레이너 라이언

푸는 중...

겹치는 사람 수는 누적합으로 쉽게 구할 수 있다.

처음에는 backtracking으로 풀려 했는데 최악의 시간인 100C50의 경우 1억을 훨씬 초과한다. 그래서 case by case를 세웠는데, 겹치는 사람 수가 n*n/2 + n%2(chessboard처럼 배열)보다 크다면 무조건 거리는 1이다.

잘 모르겠어서 구글링을 했고, 모든 경우의 탐색보다는 '거리가 d일 때 k개를 배열에 둘 수 있는가?'를 탐색하는 것으로 바꾸어 생각하면 풀린다고 한다. 생각해 보면, 새로 locker는 직전에 놓은 locker와 거리가 d인 위치에 놓게 하고(O(1)), 지금까지 놓은 locker들을 순회하면서 거리가 d 이상인지 검사해야 하고locker(O(50)) 최대 거리는 2n-1(worst 20)에 locker를 모두 놓아야 하므로(O(50)) worst O(n^5)이므로 풀릴 것으로 예상된다....

"바꿔 생각하는" 게 중요하다!

​

-> 그래서 고쳐 풀었는데도 시간초과가 난다. O(n^5)인 것 같긴 한데 call하면서 시간초과가 나는 것 같다. 어떻게 고치지?

// 몸짱 트레이너 라이언의 고민

#include <vector>
#include <algorithm>
#include <set>
#include <iostream>

using namespace std;
typedef pair<int, int> pii;

int getDist(pii&a, pii&b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}

// return {r, c} in range
bool inRange(int r, int c, int n){
    if(0 <= r && r < n && 0 <= c && c < n) return true;
    else return false;
}

// cur_point로부터 거리가 D인 모든 점
vector<pii> getDistDPoints(int D, pii cur_point, int n){
    set<pii> result;
    pii top = {cur_point.first - D, cur_point.second};
    pii bottom = {cur_point.first + D, cur_point.second};
    
    int dr[2] = {1, 1};
    int dc[2] = {1, -1};
    
    for(int i = 0; i<=D; i++){
        for(int lr = 0; lr < 2; lr++){
            pii p = {top.first + i * dr[lr], top.second + i * dc[lr]};    
            if(inRange(p.first, p.second, n)) result.insert(p);
            
            p = {bottom.first - i * dr[lr], bottom.second - i * dc[lr]};
            if(inRange(p.first, p.second, n)) result.insert(p);
        }
    }
    
    vector<pii> to_v(result.begin(), result.end());
    return to_v;
}

bool backtrack(int cur_depth, int max_depth, int target_dist, vector<pii>& results, vector<pii> cur_able_points, int n){
    if(cur_depth == max_depth-1){
        return true;
    }
    
    for(int i = 0; i<cur_able_points.size(); i++){
        pii next_point = cur_able_points[i];
        results[cur_depth] = next_point;
        
        vector<pii> dist_d_points = getDistDPoints(target_dist, next_point, n);
        vector<pii> next_able_points;
        
        for(int dpi = 0; dpi < dist_d_points.size(); dpi++){
            bool isAllDistOverD = true;
            for(int cdi = 0; cdi <= cur_depth; cdi++){
                if(getDist(results[cdi], dist_d_points[dpi]) < target_dist){
                    isAllDistOverD = false;
                    break;
                }
            }
            if(isAllDistOverD) next_able_points.push_back(dist_d_points[dpi]);
        }
        
        if(next_able_points.size() == 0) return false;
        else{
            bool flag = backtrack(cur_depth+1, max_depth, target_dist, results, next_able_points, n);
            if(flag) return true;
        }
    }
    return false;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
    // 누적합 알고리즘으로 최대 몇 명이 겹치는 지 쉽게 알 수 있음
    int start_time = 600;
    vector<int> times(721, 0);
    for(vector<int> vi : timetable){ // 시작하는 부분에 +1, 끝나는 부분에 -1을 하고
        times[vi[0] - start_time]++;
        times[vi[1] - start_time+1]--;
    }
    for(int i = 1; i<=720; i++){ // 누적합 해버리면 최대로 겹치는 사람의 명 수를 알 수 있음.
        times[i] += times[i-1];
    }
    
    // max_overlap은 worst n*n의 size임.
    // cutting ? 거리가 d인 곳에만 두는 방식 ?
    // 최대 거리 2n-1
    // 총 50번 탐색
    // 한 번의 탐색에 이전까지 둔 모든 locker를 봄 - 50번
    // n^5인 듯?
    int max_overlap = *max_element(times.begin(), times.end());
    
    int chessboard_num = n * n / 2 + n % 2; // chessboard처럼 채울 경우
    if(max_overlap == 1) return 0;
    if(max_overlap == 2) return 2 * n - 2;
    if(max_overlap > chessboard_num) return 1;
    
    vector<pii> results(max_overlap);
    int max_dist = -1, target_dist;
    vector<pii> cur_able_points;
    for(int r = 0; r<n; r++){
        for(int c= 0; c<n; c++){
            cur_able_points.push_back({r, c});
        }
    }
    for(target_dist = 2*n-3; target_dist >= 3; target_dist--){
        bool flag = backtrack(0, max_overlap, target_dist, results, cur_able_points, n);
        if(flag) break;
    }
    
    
    return target_dist;
}

/*
1명이면 0
2명이면 2n
3명이면 n?
4명이면 n
5명이면 

규칙이 없다!

일단 brute-force로 풀어야 함.

확실한 건 chessboard처럼 채울 경우가 거리가 2인 최대 선임!
그것보다 크다면 1 리턴하는 건 확실함.
*/

구글링을 좀 더 해본 결과... naive하게 접근하는 방법도 있다. 이러면 O(n^5)이다. 그냥 구현해버리면 되는 문제였네... 어쨌든 핵심은 '거리가 d일 때 몇 개 까지를 board에 둘 수 있는가?'이다.

한가지 property가 필요한데, '첫째 줄은 무조건 사용해야 한다'이다. 첫째줄을 사용하지 않는 경우 첫째 줄을 사용한 것 보다 더 적은 공간에 놓아야 하므로, 놓는게 무조건 이득인 것은 자명하다.

시작점으로부터 계속 탐색해서 거리가 d면 두고, 그렇지 않으면 다음 것을 탐색하는 방식을 반복해 간다. 그렇게 해서 끝까지 채우고 채운 것의 개수가 max_overlap을 달성하면 return해버리면 된다.. 뭔가 허무하군

시간복잡도는 6중포문이므로 O(n^6).. n이 10이므로 백만이다.

 

 

// 몸짱 트레이너 라이언의 고민

#include <vector>
#include <algorithm>
#include <set>
#include <iostream>

using namespace std;
typedef pair<int, int> pii;

int getDist(pii a, pii b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
    // 누적합 알고리즘으로 최대 몇 명이 겹치는 지 쉽게 알 수 있음
    int start_time = 600;
    vector<int> times(721, 0);
    for(vector<int> vi : timetable){ // 시작하는 부분에 +1, 끝나는 부분에 -1을 하고
        times[vi[0] - start_time]++;
        times[vi[1] - start_time+1]--;
    }
    for(int i = 1; i<=720; i++){ // 누적합 해버리면 최대로 겹치는 사람의 명 수를 알 수 있음.
        times[i] += times[i-1];
    }

    // n^5인 듯?
    // 다시 한 번 생각을 바꿔서, 'dist'가 주어졌을 때 dist를 유지하면서 최대로 넣을 수 있는 인원을 가져와 보자
    int max_overlap = *max_element(times.begin(), times.end());
    
    int chessboard_num = n * n / 2 + n % 2; // chessboard처럼 채울 경우
    if(max_overlap == 1) return 0;
    if(max_overlap == 2) return 2 * n - 2;
    if(max_overlap > chessboard_num) return 1;
    
    int target_dist;
    for(target_dist = 2*n-3; target_dist >= 3; target_dist--){
        for(int rs = 0; rs<n; rs++){
            for(int cs = 0; cs<n; cs++){
                // {rs, cs} : 탐색 시작점 / row_start, col_start
                vector<pii> lockers;
                lockers.push_back({rs, cs});

                int max_people = -1;

                for(int cr = 0; cr<n; cr++){
                    for(int cc = 0; cc<n; cc++){
                        // {cr, cc} : 현재 보는 위치 / current_row, current_col
                        bool canInsert = true;
                        for(int lockeridx = 0; lockeridx < lockers.size(); lockeridx++){
                            if(getDist(lockers[lockeridx], {cr, cc}) < target_dist){
                                canInsert = false;
                                break;
                            }
                        }

                        if(canInsert == false){
                            continue;
                        }
                        lockers.push_back({cr, cc});
                    }
                }
                if(max_overlap == lockers.size()) return target_dist;
            }
        }
    }
    
    
    return target_dist;
}