[프로그래머스] Lv2 - 구명 보트
접근 방식이 문제는 짝짓기 문제 유형이라고 생각합니다.정렬을 해서 순차적으로 몸무게가 가벼운 사람들끼리 짝을 짓게 되면 틀리는 문제입니다.반례는 다음과 같습니다. (단, 보트가 실을 수 있는 최대 무게는 100 입니다.)people : [30,30,70,70,40]answer : 3 제일 몸무게가 적게 나가는 사람들끼리 묶어주는 방식으로 풀게 되면 아래와 같이 됩니다.(30,30), (40), (70), (70) 보트가 4개가 필요하게 됩니다. 하지만 최소의 보트 갯수는 3개 이므로, 정답이 아닙니다. 선택한 두 사람의 무게의 합이 보트가 실을 수 있는 최대 무게에 근접하도록 짝지어야 합니다.(30,70), (30,70), (40) 이렇게 짝을 지어주면 3개의 보트로 모든 사람을 나를 수 있습니다. 어떤..
2025. 2. 13.
