[프로그래머스] 42885 구명보트

프로그래머스 level2

문제

문제 풀이

문제 리뷰

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 문제이다.
최솟값을 만족할 수 있는 조건은 무게의 최대값-최소값을 비교하는 것이다.

최대값-최소값 조합임에도 불구하고 무게 제한에 걸린다면
최대값인 사람은 혼자 구명보트에 탈 수 밖에 없다.
그래서 배열을 오름차순으로 정렬해주고
최소값(앞, i)에서 최대값(뒤, j)를 차례로 비교해보는 것이다.

무게 제한에 걸린다면 count 증가, j 감소
무게 제한에 걸리지 않는다면 count 증가, i 증가, j 감소

두 조건 모두 count 값은 증가된다.
한명만 타게 되거나 두명이 타게 되든 구명보트의 수는 추가된다.
현재 최대값 index인 j를 감소시켜주는 것 또한
혼자 타거나 둘이서 타도 해당 최대값은 구명보트에 탔기 때문에 감소시켜준다.

반복문은 i보다 j가 클 동안만 반복된다.
i와 j가 같은 index를 바라본다는 건 모두 한사람을 가리키고 있다는 것이다.
한사람을 가리킬 때, 반복문으로 들어가게 되면 한사람을 가지고 조합을 만들게 되기에
애초에 차단하는 것이다.

i와 j가 같을 경우는 반복문 밖에서 따로 처리해준다.
이 경우는 결국 모든 사람이 각자 구명보트를 타게 된 경우를 의미한다.
마지막 남은 사람의 수가 반복문에서 카운팅 되지 못했기 때문에
밖에서 따로 count 값을 증가시켜준다.

TMI

오전 알고리즘 풀이^ㅁ^

1일 1알고리즘 완료🤓