[C++] 백준 1092번 풀이 ( 배 )

정민경·2023년 7월 10일
0

baekjoon

목록 보기
38/57
post-thumbnail

- 문제 (1092번) : 배

  • crane 이 옮길 수 있는 최대 무게와, 옮기려고 하는 box 의 무게가 주어졌을 때 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램 작성.

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 crane 의 개수 N 입력 ( N ≤ 50, 자연수 )
  • 둘째줄에 공백을 사이에 두고 N 개의 crane 이 옮길 수 있는 최대 무게 입력

  • 셋째 줄에 옮길 박스의 수 M 입력 ( M ≤ 10,000, 자연수 )
  • 넷째 줄에 M 개 각각의 box 의 무게 입력

[ 출력 ]

  • 모든 박스를 배로 옮기는데 드는 시간의 최솟값 출력.
    -> crane 을 한번 쓸때마다 1이라는 시간 사용
  • 만약 모든 박스를 옮길 수 없다면 -1 출력

- 문제 풀이

  • 이 문제는 입력받은 box 를 무게의 내림차순으로 정렬한 후 가장 앞에서부터 탐색을 하면서 가장 무거운 무게를 들 수 있는 크레인을 사용해 박스를 옮긴다.

    이러한 과정을 box 가 빌 때 까지 반복한다.

  • 나는 이 문제를 배열을 사용해 해결했다. ( 동적으로 사용할 수 있는 vector 를 사용했다고 말하는게 더 정확하다. )

  1. 일단 crane 을 담을 vector 와 box 를 담을 vector 각각 생성한다. ( 총 두개의 vector 생성 )

  2. 그 후 crane 과 box vector 를 모두 내림차순으로 정렬. 즉, 가장 무거운 것 -> 가벼운 것 순으로 나열

  3. 그 후 box 를 옮길때마다 vector 에서 제거를 해주는데 box vector 가 빌 때까지 box 를 옮겨준다.
  • 위와 같은 과정을 수행해 결과를 해결한다.

  • 이 때 어떤 순서로 box 를 옮길것인가가 가장 중요한 문제인데, 나는

    1. while 문을 사용해 box 가 빌때까지 반복해주었고,
    2. crane 에서 가장 무거운 무게를 옮길 수 있는 crane 부터 사용해 옮길 수 있는 box 중 즉, 남은 box 중 crane 이 옮길 수 있는 최대 무게부터 옮기도록 하였다.
    3. crane 을 돌 때 하나의 crane 이 하나의 box 를 옮겼다면, 다음 crane 이 옮길 box 를 선택하도록 하였다.
    4. 모든 crane 을 다 돌면 count 를 1 증가시키고 2 ~ 4 번 반복
  • 위와 같은 과정을 box vector 가 빌때까지 반복한 후 계속 저장됐던 count ( 나의 code 상 result ) 를 출력시키면 문제 해결!


- 최종 코드

0개의 댓글