22.06.18. 풀었던 문제들

1. 캠핑

처음에는 O(n^2)으로 풀어야 하는 문젠데, 어떻게 O(1)또는 O(logn)만에 좌표가 사각형 안에 있는 걸 판별하지 ? 라고 생각했다. 이렇게 판별하려면 좌표평면 안에 모든 좌표에 대한 정보를 넣어야 하는데 좌표의 범위가 int이므로 이 또한 불가능했다.

잘 모르겠어서 구글링 해 보니 좌표압축 후 누적합으로 푸는 문제였다. 좌표압축은 처음 들어보는 알고리즘이다! 신박했다.

https://puzzle-puzzle.tistory.com/entry/2017-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%BD%94%EB%93%9C-%EC%98%88%EC%84%A0-%EC%BA%A0%ED%95%91

// 캠핑

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

using namespace std;


typedef pair<int, int> pii;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {    
    // 좌표 압축
    set<int, less<int>> rset, cset;
    for(int i = 0; i<n; i++){
        rset.insert(data[i][0]);
        cset.insert(data[i][1]);
    }
    
    // row 좌표 압축 후 mapping
    vector<int> compressed_r(rset.begin(), rset.end());
    map<int, int> rmapper;
    for(int i = 0; i<compressed_r.size(); i++){
        rmapper[compressed_r[i]] = i;
    }
    
    // col 좌표 압축 후 mapping
    vector<int> compressed_c(cset.begin(), cset.end());
    map<int, int> cmapper;
    for(int i = 0; i<compressed_c.size(); i++){
        cmapper[compressed_c[i]] = i;
    }
    
    // mapping된 좌표로 변경
    for(vector<int> &vi : data){
        vi[0] = rmapper[vi[0]];
        vi[1] = cmapper[vi[1]];
    }
    // 좌표 압축 완료
    
    // psum[i][j] : {0, 0} ~ {i, j}까지 쐐기의 개수 ({i, j}는 미포함)
    // 누적합으로 구할 수 있음
    int maxnum = 5001;
    vector<vector<int>> psum(maxnum, vector<int>(maxnum, 0));
    
    for(vector<int> &vi : data){
        psum[vi[0]][vi[1]] = 1;
    }
    
    // 누적합 기본 설정
    for(int i = 1; i<maxnum; i++){
        psum[i][0] = psum[i-1][0];
        psum[0][i] += psum[0][i-1];
    }
    for(int r = 1; r<maxnum; r++){
        for(int c = 1; c<maxnum; c++){
            psum[r][c] += psum[r-1][c] + psum[r][c-1] - psum[r-1][c-1];
        }
    }
    
    // 구하기
    int answer = 0;
    for(int i = 0; i<n; i++){
        for(int j = i+1; j<n; j++){
            int rmin = min(data[i][0], data[j][0]);
            int rmax = max(data[i][0], data[j][0]);
            int cmin = min(data[i][1], data[j][1]);
            int cmax = max(data[i][1], data[j][1]);
            
            if(rmin == rmax || cmin == cmax) continue;
            
            int num_wedge = psum[rmax - 1][cmax - 1] - psum[rmax - 1][cmin] - psum[rmin][cmax - 1] + psum[rmin][cmin];
            if(num_wedge == 0) answer++;
        }
    }
    
    return answer;
}

/*
어떤 점 2개를 골랐을 때 그 사이에 있는 점만 고르는 방법이 없을까?
이게 핵심
인풋이 5천이니 n^2으로 풀어라는 말인데...
data의 조합을 구하는 것 만으로도 이미 n^2임
그러면 1개의 조합을 구했을 때, 설치 가불(안에 뭔가 있는지)를 O(logn)으로 구할 수 있는가?
좌표 압축으로 쉽게 구할 수 있다네요~ 
*/

 

2. 몸짱 트레이너 라이언

푸는 중...

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

처음에는 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)이므로 풀릴 것으로 예상된다....

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