[25.03.18] algo 백준 12762 리뷰

25.03.31(Mon) 알고리즘 스터디 리뷰

백준 비행기 전시 풀러가기

백준 비행기 전시 문제 풀이

조건 요약

기본 설정:

• 두 대의 비행기가 0번과 1번 위치에 전시됨
• 비행기를 서로 바꾸기 위해 부품들을 분해하여 옮겨야 함
• 부품 운송을 위한 트럭이 1대 있음
• 트럭이 한 위치에서 다른 위치로 이동하는 데 T시간 소요

조건들

• 총 N개의 부품을 옮겨야 함
• 트럭의 최대 적재량은 M
• 부품은 운송 준비되는 순서대로 번호가 매겨짐
• 트럭은 최대한 많은 무게를 싣고 이동함
• 부품이 트럭 여유 공간보다 크면 분해해서 일부만 실을 수 있음
• 도착 시 모든 부품을 내리고, 준비된 부품을 최대한 싣고 다시 출발
• 양쪽에서 동시에 부품이 준비되면 현재 위치의 부품을 먼저 싣음
• 현재 위치에 운송할 부품이 없으면 반대편으로 이동

풀이 방식

구현을 매우 심도 있게 해야하는 문제였다. 여기서 분기점이 매우 복잡해서 풀면서도 테스트 케이스를 여러가지를 생각해봐야 하는 문제였다. 내 풀이의 경우에서는 트럭에 여러가지를 실어야 할때 남은 크기가 0인 경우도 실어버린다고 생각하는 부분을 예외적으로 처리해 주지 못한 부분이 있었다. 그 부분을 제외하고는 구현을 잘 생각하고 풀이하면 되는 문제였다.

정답 코드