[Algorithm] Programmers :: 캠핑

https://school.programmers.co.kr/learn/courses/30/lessons/1833

프로그래머스

 

bool cmp(const vector<int>& a, const vector<int>& b)
{
    if (a[0] == b[0])
    {
        return a[1] < b[1];
    }
 
    return a[0] < b[0];
}
 
int solution(int n, vector<vector<int>> data) 
{
    int answer = 0;
 
    sort(data.begin(), data.end(), cmp);
 
    for (int i = 0; i < n; ++i)
    {
        int sy = data[i][0];
        int sx = data[i][1];
 
        for (int j = i + 1; j < n; ++j)
        {
            int ny = data[j][0];
            int nx = data[j][1];
            bool isCheck = false;
 
            if (sy == ny || sx == nx) continue; // 같은 행,열이면 넘기기. 한직선이라 넓이 0
 
            for (int k = i + 1; k < j; ++k) // 사이에 다른 점있는지 체크.
            {
                int cy = data[k][0];
                int cx = data[k][1];
                int maxX = max(sx, nx);
                int minX = min(sx, nx);
 
                if ((cy > sy && cy < ny) &&
                    (cx > minX && cx < maxX)
                    )
                {
                    isCheck = true;
                    break;
                }
            }
 
            if (!isCheck) ++answer;
        }
    }
 
    return answer;
}

 

뭔가 백트래킹으로 풀 수 있지 않을까? 해서 몇시간동안 볼펜으로 애꿎은 노트만 괴롭혔던 문제

3레벨짜리라 그래도 위의 코드처럼 풀면 당연히 시간초과에 걸릴 줄 알고, 그냥 처음부터 배제했었다.

근데 뭔가 그럴듯한 백트래킹 풀이가 나오는 듯 하면서도, 예외상황이 하나씩 나와서 결국 포기했다.

그래서 그냥 완전탐색처럼 코드 짜고 제출했더니 통과가 되긴 했다.

 

근데 시간 4400ms대가 나오는데;;; 제한시간을 몇초로 잡아놨는지 모르겠다