[Python] 백준 1092 배

문제 링크 : https://www.acmicpc.net/problem/1092

1092번: 배

1. 접근 방법

전형적인 그리디 문제 중 하나라고 생각한다.

해결 방법은 다양하게 고민하기는 했지만, 잘 떠오르지 않아 브루트 포스로 해결했다.

 

2. 풀이 코드

🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/1000/1000/1092.py

GitHub - mintropy/baekjoon_py

📕코드 해설

모든 값을 입력 받아 내림차순 정렬했다. 정렬의 방향은 어떤 방향이던 상관 없을 것이라 생각하지만, 내림차순 정렬이 코드 구현이 편할 것 같아서 선택했다.

크레인의 가능한 최대 무게를 넘어선 박스가 있으면 불가능하므로, 처리해주었다.

 

이후, 확인은 모든 크레인에 대해, 모든 박스를 확인하는 방법도 있지만, 조금이라도 탐색을 줄일 수 있지 않을까 생각하여, 각 크레인 별 가능한 최대 무게 박스 인덱스를 저장한 리스트를 기준으로 탐색했다.

그리고, 각 박스를 옮겼다면 그 확인을 개별 리스트를 활용할수도 있지만, 따로 생성하지 않고 기존 박스 무게를 저장한 리스트에서 값을 0으로 바꾸는 방식으로 선택했다.

그러면 다음과 같은 경우의 수로 나뉜다.

① 지금 인덱스의 박스가 아직 옮겨지지 않은 경우, 박스를 옮긴다

② 지금 인덱스의 박스가 옮겨진 경우, 인덱스를 더하며 옮겨지지 않은 박스를 찾는다

③ 만약 인덱스가 전체 박스의 개수 M과 같아지면 더 적거나 같은 무게 제한이 걸린 모든 크레인은 확인하지 않는다(break)

그리고 모든 크레인에 대하여 위의 작업을 몇 회 확인하는지, 즉 크레인의 수 N에 대하여 for문이 호출되는 횟수가 이 문제에서의 정답이 된다.

 

3. 생각 정리

조금 더 고민하더라도, 그리디로 해결하지 못한것은 조금 아쉽게 느껴진다.

그래도 나름 재밌는 방법으로 해결했다고 생각하지만, 내 코드를 조금 더 효율성 높은 코드로 구현할 수 있지 않을까라는 생각은 남는다.