〈전역 역전〉 문제 출제자 해설

〈2024 상반기 전남대학교 PIMM 알고리즘 파티〉 대회 출제분

군 복무 도중에는 국방부의 시계가 정말 느리게 흘러갑니다. 군부대 바깥에서의 하루하루가 정말 소중하기 때문에, 어떤 장병들은 꽤 많은 것을 지불하거나 희생하더라도 휴가를 더 얻어내려고 하기도 합니다. 저는 코로나 범유행이 마무리되어 각종 정책들이 원상태로 돌아올 때 복무했기 때문에, 제 세대 즈음부터 휴가를 모아 조기전역 하는 것이 불가능한다던지, 제 몇 세대 앞부터 영창이 군기교육대로 전환되었다던지, 하는 과도기적인 시기였습니다.

풀이

문제에서 제시하는 세 개의 쿼리는 모두 종현과 영도 사이의 상대적인 전역일 차이를 축소시킵니다. 이 문제에서는 전역일 차이를 물어보므로, 세 개 쿼리 모두 영도의 전역을 앞당기는 것으로 처리할 수 있습니다.

종현의 전역일을 늦추는 쿼리, 영도의 전역일을 앞당기는 쿼리를 모두 영도의 전역을 앞당기도록, 혹은 종현의 전역을 뒤로 미루도록 통일해 처리한다면, 이 문제는 전형적인 0-1 냅색 문제로 확인할 수 있습니다.

• 조기 전역: $D$ 일만큼 영도의 전역을 앞당기는 것으로 처리합니다.
• 군기교육대: $D$ 일만큼 영도의 전역을 앞당기는 것으로 처리합니다.
• 임기제 부사관: $M \times 30$ 일만큼 영도의 전역을 앞당기는 것으로 처리합니다.