Shoemaker’s Problem

by SL

나의 시간과 에너지를 쏟아부을 뭔가가 필요한 꿀꿀한 일요일 오후, 이 문제를 풀기로 했다.

Shoemaker’s Problem

내일까지 못 풀면 팀원들에게 커피를 사야 하기 때문은 아니고(…) 진짜로 정신력을 소모할 거리가 필요했다. 정말로 진짜다.

벌금을 최소화하는 스케줄을 찾으라고? 어쩐지 Dynamic Programming의 향기가 난다. 그럼 일단 문제를 쪼개 보자. Job을 A, B, C, …라고 하고, {A, B, C}를 가장 효율적으로 처리했을 때의 벌금(fine) 총합을 S(ABC)라고 하면,

S(AB), S(BC), S(AC)는 쉽게 구할 수 있고,
S(ABC) = minimum( S(A) + S(BC) , S(B) + S(AC) , S(C) + S(AB) )
S(ABCD) = minimum( S(A) + S(BCD) , S(B) + S(ACD) , S(C) + S(ABD) , S(D) + S(BCD) )

응? 좀 이상한데? 전형적인 Dynamic Programming 문제라면 이런 식으로 경우의 수가 늘어나면 안 되는데.. 내가 잘못 짚었나?

그럼 Greedy Algorithm을 써보자. 매 선택의 순간마다 가장 벌금을 적게 내는 Job을 고르는 거다.

예제 문제에서 두 번째 (1, 1000)은 빼고

3 4 (Job A)
2 2 (Job B)
5 5 (Job C)

만 놓고 생각해보자.
A를 골랐을 때 포기해야 하는 벌금은 3 days * (2 + 5) cents = 21
B를 골랐을 때, 2 days * (4 + 5) cents = 18
C를 골랐을 때, 5 days * (4 + 2) cents = 30

그러면 B를 고르고, 다음에는

3 4 (Job A)
5 5 (Job C)

A를 고르면 15, C를 고르면 20, 따라서 A, C의 순서대로 한다. 그러면 최종 답은 BAC.

헉? 정답은 ABC라고?? 내가 또 뭘 잘못했나? 아니야, 예제의 답이 틀렸을 거야. 내가 증명해 주마.

(잠시 후) 진짜로 ABC로 하는 게 총 벌금이 가장 적네. 반례를 찾았으므로 증명은 실패. 다시 처음부터 생각해보자.

분명히 Induction을 써서 푸는 문제 같은데… 만약 예제에서 Job이 A와 B만 있다면, 정답은 AB의 순서로 일을 하는 거다 . AB의 순서로 처리했을 때 내야 하는 벌금을 F(AB)라고 하면 다음과 같이 쓸 수 있다.

F(AB) < F(BA)

이렇게 Job이 두 개만 있을 때는 간단하다. 그런데 여기에 C가 추가되면??

F(CAB), F(ACB), F(ABC)를 다 따져보는 건 너무 무식한데..

아, 만약에 F(BC) < F(CB)이면 어떻게 되지?

F(AB) < F(BA) and F(BC) < F(CB)이면 F(AC) < F(CA)가 만족하나?

응, 만족한다. (매우 간단하게 증명할 수 있으나, 블로그에 공간이 부족하므로 자세한 설명은 생략)

자, 정리해보자. 그럼 F(AB) < F(BA) and F(BC) < F(CB) 일 때 {A, B, C}에 대한 최적의 스케줄을 찾는 문제가 되었다.

(손가락이 간질거리기 시작한다.)

근데, 이런 조건이라면 당연히 F(ABC), 즉 A, B, C의 순서대로 일을 하는 게 가능한 모든 조합 중에 가장 최적의 답 아냐? 맞잖아. 아닐 수도 있다고? 맞다니깐. 그럼 증명해봐.

당연한 것 같은데 증명하지 않으면 계속 찝찝할 것 같지만 그래도 그냥 직관에 의존해보자면, 아래의 부등식처럼 다른 Job은 그대로 놓고 인접한 두 개씩만 바꿔서 비교해 보면 다른 어떤 조합보다 F(ABC)의 벌금이 최소라는 걸 보일 수 있을 것 같다.

F(ABC) < F(ACB) < F(CAB) < F(CBA)
F(ABC) < F(BAC) < F(BCA)

그러면 결국 이 문제는 A, B, C, … 이렇게 N개의 Job이 있을 때, 두 개의 Job끼리 우선순위를 비교해서 가장 급한 것부터 하나씩 해나가면 풀리는 Greedy Algorithm 문제였구나. 그럼 뭐야. Job 두 개를 비교하는 함수 하나만 만들면 되잖아. 정렬하는 알고리즘은 C 표준 라이브러리에서 제공하는 qsort()가 있으니까.

코딩은 금방 끝이 났고, 문제 사이트에 코드를 제출했다.

어라? Wrong Answer라고? 그럴 리가… 나의 알고리즘은 완벽해! 아무리 머리를 굴려도 원인을 찾을 수가 없어서 결국 검색해 봤다. 헐.. 출력에서 줄을 바꿀 때 “\r\n”을 하면 안 되고 “\n”만 써야 하는구나. 출력 형식을 제대로 맞추니까 “Accepted”가 오네. 훗, 역시 나는 틀리지 않았어.

결과를 보니 내 코드는 0.004초 정도 걸렸는데, 이 정도로 순위권을 넘보는 건 언감생신. 어떻게 된 게 전부 0.000초냐..