[BOJ] 1931_회의실배정_문제풀이

걸린시간 : 1시간 30분

 

문제풀이 접근 : 일단 100000이라는 N값을 받아야하니 최소 NlogN으로 접근해야겠다고 생각했다. 또한 int값 x,y를 갖고있는 객체가 필요하다고생각했다. 메모리값은 괜찮았다고 생각했다. 

 

이 문제의 핵심은 얼마나 많은 회의실을 사용할수 있냐? 인거같다. 최대한 많이 이용해야겠다 생각하며 이용시간을 최대한 최소로 이용하는 회의실이 최소라고 생각했다. 

 

이용시간을 최대한 최소로 이용한다면 많은 회의실을 배정할수 있으니까 말이다. 순서대로 가야된다는말이고 나는 처음부터 순서대로 회의실을 체크해야하고 이를 위해 Comparable 객체를 사용해야겠다고 생각했다. 

 

이후 내가 선택한 회의실은 최소한의 시간을 사용한 회의실이라고 생각을해야했다. 그 이유는 다음 회의실의 시간은 모르며 지금 내가 선택한 회의실이 최소한이라고 생각해야했다. 그 이후는 다음 회의실 이용시간에 내가 고른 회의실 시간안에서 최소한의 회의실을 이용하는지 체크해야했다고 생각한ㄷ. 그렇지 않다면 넘어가는 로직을 말이다. 하지만 내가 고른 회의실의 이용시간을 넘어가야 회의실 증가를해야한다. 

 

즉 내가 현 시점에서 고른 회의실이 다음 회의실에 영향을 미치냐 미치지 않느냐가 중요한거같다. 그 이유는 뭐라고 생각해야하냐 

내가 현시점에서 고른 회의실이 끝나는시간보다 다음 회의실이 끝나는 시간보다 작다면 현재 내가 고른 회의실이 이용시간을 최대한 최소로 이용해야하기때문에 교체해야한다고 생각했기때문이다. 즉 내가 고른 회의실이 최소로 이용가능하냐?가 핵심인거같다.

 

이 문제에선 회의실 교체와 회의실 바꿈만이 존재하는거같다.

교체 -> 내가 갖고있는 회의실 끝나는시간보다 다음회의실 끝나는시간보다 크다 (하지만 시작시간은 끝나는시간보다 작아야함)

추가 -> 내가 갖고있는 회의실 끝나는시간보다 다음회의실 시작시간이 더 크다 

 

이런생각을 가지고 접근했다 글을 쓰며 생각하기를 만약 정해진 시간내에 많은 회의실을 필요로한다면 내가 갖고있는 것보다 남의 회의실의 시간을 고려하여 문제를 풀수있겠다라는 생각이든다.

 

정해진 틀안에 많은것을 해야한다면 내가 갖고있는게 과연 최소한인가? 라는 것을 기억해둬야겠다.