[BOJ #1700] 멀티탭 스케줄링

BOJ #1700, 멀티탭 스케줄링 문제입니다.

 

계속 알고리즘을 풀긴 풀었지만 귀찮은 탓에 블로그는 못 썼습니다. 학교 과제로 바쁘기도 하고, 역시 24학점은 아무나 듣는 게 아닌 것 같습니다. 다음 학기는 학점을 좀 널널하게 들으면서 편한 마음으로 학교를 다니기로 생각했습니다. 그러면서 겨울방학부터 군입대 전까지는 자기계발에 몰두하려고 합니다.

 

꽤 오랜 시간 고민했던 문제고, 그리디는 참 어렵습니다. 물론 이 문제의 그리디 판단 기준은 상당히 간단해서 해설을 본다면 누구나 바로 이해하겠지만, 꾹 참고 혼자 생각해 보느라 꽤 크게 돌아서 온 것 같습니다. 그리디는 구현이 어렵다기보단, 문제가 그리디로 풀린다는 사실을 인지하는 것이 정말 어렵습니다.

접근

일단 기본적으로 쉽게 생각할 수 있는 사실들을 떠올렸습니다.

• 멀티탭이 비어 있다면, 꽂는다.
• 멀티탭에 사용하려는 전기용품이 있다면, 사용한다.
• 멀티탭이 꽉 찼다면, 가장 먼저 앞으로 더 이상 사용하지 않는 것을 뺀다.

다음으론 그 후의 상황(멀티탭이 꽉 찼고, 모두 다음에 사용할 전기용품인 경우)에 대해서 최대한 여러 가지 기준을 생각해 보았습니다.

• 가장 적게 쓰는 것부터 뺀다.
• 늦게까지 쓰는 순으로 정렬 후, 앞에서부터 뺀다.
• 일찍 쓰는 순으로 정렬 후, 뒤에서부터 뺀다. = 급하지 않은 것부터 뺀다. (정답)

이 세 가지 기준을 생각해 보았는데, 사실상 직관적으로도 세 번째가 맞다고 생각됩니다만 어째서인지 풀 때는 첫 번째, 두 번째를 모두 거쳐 멀리 돌아왔습니다. 세 번째 기준에 대한 검토는 다음과 같이 해 보았습니다.

기준에 대한 검토 - 전제

멀티탭의 구멍은 많을 수록 좋다. = 플러그를 조금 뺄 수 있게 된다.

기준에 대한 검토 - 증명

(해당 시점에서) 가장 빨리 쓰는 순으로 전기용품을 정렬했다고 하자. 맨 마지막의 전기용품 A이 시각 TA에 사용되기 시작한다고 하면, 반대로 말해 TA 전까지는 해당 전기용품이 사용되지 않는다는 것이 된다.

만약 해당 전기용품이 TA 전에 멀티탭에 있다면, 그것은 멀티탭의 구멍이 하나 적어진 것이다. (꽂혀 있다 = 빼기 전까지 아무 전기용품도 꽂을 수 없다 = 구멍이 없다)

만약 또 다른 전기용품 B은 시각 TB에 사용되기 시작한다고 치자(당연히 TB < TA이다). A와 B가 둘 다 멀티탭에 꽂혀 있고 새로운 전기용품의 사용을 위해 둘 중 하나를 뽑아야 하는 상황인 것이다.

 

B를 뽑으면 TA의 시간동안 멀티탭의 구멍이 하나 적은 것이 된다.
그런데 A를 뽑으면 TB의 시간동안 멀티탭의 구멍이 하나 적은 것이 된다.
즉, A를 뽑으면 멀티탭의 구멍이 하나 더 많은 시간이 B를 뽑는 것보다 TA - TB만큼 많아진다.

따라서 A를 뽑아야 한다.

구현

사실 알고리즘은 매우 간단해서 구현도 쉬울 것이라고 생각했는데, 막상 짜 보고 나니 구현이 어려웠다기보단 제가 구현을 잘 못한다는 생각이 들었습니다. 나름 여러 가지 테크닉은 있지만 코드 자체가 명료하지 않고 상당히 난잡한 느낌이 듭니다. 다른 분들의 코드를 보고 배워가는 시간을 가져봐야겠습니다.