- 문제 (1092번) : 배
- crane 이 옮길 수 있는 최대 무게와, 옮기려고 하는 box 의 무게가 주어졌을 때 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램 작성.
- 입력 및 출력
[ 입력 ]
- 첫째 줄에 crane 의 개수 N 입력 ( N ≤ 50, 자연수 )
- 둘째줄에 공백을 사이에 두고 N 개의 crane 이 옮길 수 있는 최대 무게 입력
- 셋째 줄에 옮길 박스의 수 M 입력 ( M ≤ 10,000, 자연수 )
- 넷째 줄에 M 개 각각의 box 의 무게 입력
[ 출력 ]
- 모든 박스를 배로 옮기는데 드는 시간의 최솟값 출력.
-> crane 을 한번 쓸때마다 1이라는 시간 사용- 만약 모든 박스를 옮길 수 없다면 -1 출력
- 문제 풀이
-
이 문제는 입력받은 box 를 무게의 내림차순으로 정렬한 후 가장 앞에서부터 탐색을 하면서 가장 무거운 무게를 들 수 있는 크레인을 사용해 박스를 옮긴다.
이러한 과정을 box 가 빌 때 까지 반복한다.
-
나는 이 문제를 배열을 사용해 해결했다. ( 동적으로 사용할 수 있는 vector 를 사용했다고 말하는게 더 정확하다. )
- 일단 crane 을 담을 vector 와 box 를 담을 vector 각각 생성한다. ( 총 두개의 vector 생성 )
- 그 후 crane 과 box vector 를 모두 내림차순으로 정렬. 즉, 가장 무거운 것 -> 가벼운 것 순으로 나열
- 그 후 box 를 옮길때마다 vector 에서 제거를 해주는데 box vector 가 빌 때까지 box 를 옮겨준다.
-
위와 같은 과정을 수행해 결과를 해결한다.
-
이 때 어떤 순서로 box 를 옮길것인가가 가장 중요한 문제인데, 나는
- while 문을 사용해 box 가 빌때까지 반복해주었고,
- crane 에서 가장 무거운 무게를 옮길 수 있는 crane 부터 사용해 옮길 수 있는 box 중 즉, 남은 box 중 crane 이 옮길 수 있는 최대 무게부터 옮기도록 하였다.
- crane 을 돌 때 하나의 crane 이 하나의 box 를 옮겼다면, 다음 crane 이 옮길 box 를 선택하도록 하였다.
- 모든 crane 을 다 돌면 count 를 1 증가시키고 2 ~ 4 번 반복
-
위와 같은 과정을 box vector 가 빌때까지 반복한 후 계속 저장됐던 count ( 나의 code 상 result ) 를 출력시키면 문제 해결!
- 최종 코드
