🔗 링크
//programmers.co.kr/learn/courses/30/lessons/42885
🛶 문제
두 명씩 옮길 수 있는 구명보트가 있다.
구명보트는 무게에 한계가 있고, (limit)
👀 예제로 문제 파악하기
입력 : people [70, 50, 80, 50], limit 100
최소한의 횟수로 옮기기 위해서는 가장 몸무게가 큰 사람 + 가장 몸무게가 작은 사람 조합이여야 한다.
위 예제같은 경우에는
- 80 (최솟값인 50과 같이 가면 한계점인 100을 넘는다.)
- 70 (최솟값인 50과 같이 가면 한계점인 100을 넘는다.)
- 50 + 50
순으로, 총 횟수인 3을 return한다.
입력 : people 50, 30, 20, 70, 10, limit 100
- 70 + 10
- 50 + 20
- 30
😮 알고리즘 풀이 순서
max는 정렬된 배열의 맨 끝에서, min은 맨 처음에서 시작.
max + min이 limit을 넘으면 혼자 가는 것으로, 넘지 않으면 두 개가 함께 가는 것으로 처리
50 + 80은 limit인 100을 넘으니 80 혼자 간다.
50 + 70도 마찬가지
50 + 50은 limit인 100과 같으므로 둘이 갈 수 있음
둘이 간다는 차리를 하기 위해 min을 1 누적해준다.
배열 people을 정렬한다.
min은 0으로 초기화해준다.
- 최솟값의 위치의 역할
반복문을 돈다.
- 초기값 max는 people
배열의 크기 -1
- max는 최댓값 위치의 역할 - min ≤ max일 때까지 반복
- 최솟값의 위치가 최댓값의 위치보다 커지면 반복 종료 - max—
- 초기값 max는 people
배열의 크기 -1
반복문
- people의 min 위치에 있는 값 + max 위치에 있는 값이 limit보다 작거나 같으면 min++.
- answer++
- 위 if문에서 걸리지 않으면 현재 최댓값 혼자 구명보트를 탄 걸로 처리