[프로그래머스/C++] 몸짱 트레이너 라이언의 고민 (2017 카카오코드 본선)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 봤을 때, 규칙을 찾아보려고 생각했다.

 

규칙을 찾을 경우 인원이 최대 몇명 겹치는지 알면 쉽게 풀 수 있을 것 같았기 때문이었다.

 

인원이 최대 몇명 겹치는지를 계산하기 위해서 운동 시작시간을 기준으로 정렬을 한다.

 

운동이 끝나는 시간을 pq에 삽입하고, pq에 들어있는 시간이 다른 사람의 운동 시작 시간보다 빠르다면 그 사람은 운동이 끝났으므로 pq에서 빼준다.

 

이때 pq의 크기가 max인 경우가 최대 사람 수다.

 

 

하지만, 2명인 경우와 사람의 수가 n*n/2+n%2 보다 큰 경우를 빼고는 규칙을 찾기 힘들었다.

 

그래서 다음으로 생각한 풀이는 2명 이상일 경우에 최대 거리가 2*(n-1)이하로 나오기 때문에 특정 거리를 기준으로 최대 인원을 캐비넷에 배치할 수 있는지 판단해야겠다고 생각했다.

 

예를 들어 예상 최소거리가 4라면 최대로 겹치는 인원들 사이의 거리가 4 이상이 될 수 있는지 검사하면 된다.

만약 불가능할 경우 거리를 3으로 줄여서 다시 검사하면 된다.

 

그러나 문제는 풀리지 않았다.

 

(0, 0) 이 가장 구석이기 때문에 0, 0에서 시작하는 경우가 거리가 항상 멀 것이라고 생각했다.

 

그렇게 여러 테스트 케이스를 넣으면서 생각할 수 있는 경우를 넣어봤지만, 통과가 되지 않았다.

광기의 흔적;;

 

중간에 풀다보니 최소가 되기 위해서 가장 끝 줄을 사용하는 것은 맞지만, 구석에 캐비넷을 배치하지 않는 경우도 있을 것이라는 생각이 들었다.

그래서 맨 윗줄을 시작점으로 잡아서 n*(n*n) 번 탐색을 했더니 성공했다...

 

​

[아이디어 정리]

1. 운동하는 사람들을 시작시간으로 정렬하고 pq를 이용해 최대 사용 인원을 구한다.
2. 최대 사용인원이 1이하면 0을 return한다.
3. 최대 사용인원이 2 이상이라면, 2*(n-1) [최대거리]부터 1까지 거리를 기준으로 사용인원들을 캐비넷에 배치할 수 있는지 탐색한다.
4. 탐색할 때, 첫 줄의 모든 점을 시작점의 후보로 두고 특정 거리만큼 인원들의 배치가 가능한지  탐색한다.

 

 

Code

 

 

#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
    int answer = 0;
    sort(timetable.begin(),timetable.end(),[](vector<int> a,vector<int>b){
        return a[0]==b[0]?a[1]<b[1]:a[0]<b[0];
    });
    priority_queue<int,vector<int>,greater<int>> pq;
    int maxPeople=0,nn=0;
    for (int i=0; i<m; i++)
    {
        if (pq.empty())
        {
            pq.push(timetable[i][1]);
            nn=pq.size();
            maxPeople=max(maxPeople,nn);
        }
        else
        {
            while (!pq.empty()&&pq.top()<timetable[i][0])
            {
                pq.pop();
            }
            pq.push(timetable[i][1]);
            nn=pq.size();
            maxPeople=max(maxPeople,nn);
        }
    }
    if (maxPeople<=1)
    {
        return 0;
    }
    int cnt=0;
    for (int dist=2*(n-1); dist>=1; dist--)
    {
        for (int xx=0; xx<=n/2; xx++) //절반만 탐색해도 대칭이라 완전 탐색이 가능하다
        {
            vector<vector<bool>>cabi(n,vector<bool>(n,true)); //캐비넷
            cnt=maxPeople;
            for (int i=0; i<n; i++)
            {
                for (int j=0; j<n; j++)
                {
                    if (abs(i)+abs(xx-j)<dist)
                    {
                        cabi[i][j]=false;
                    }
                }
            }
            cnt--;
            for (int y=0; y<n; y++)
            {
                for (int x=0; x<n; x++)
                {
                    if (cabi[y][x])
                    {
                        for (int i=0; i<n; i++) //새로운 인원이 들어온 주변에 못들어오게 처리
                        {
                            for (int j=0; j<n; j++)
                            {
                                if (abs(y-i)+abs(x-j)<dist)
                                {
                                    cabi[i][j]=false;
                                }
                            }
                        }
                        cnt--;
                    }
                }
            }
            if (cnt<=0)
            {
                return dist;
            }
        }        
    }
    return answer;
}

 

---

푸는데 오래 걸렸던 문제다...

예외 케이스가 있을 것 같았는데, 찾지 못해서 없을 것이라고 생각하고 계속 고민을 했다...

완전탐색을 할 때, 함부러 탐색의 범위를 제한하는 것을 조심하자..

프로그래머스