Programmers - 구명보트

---

title: Programmers - 구명보트
date: 2022-06-23
tags:

• Algorithm

---

https://programmers.co.kr/learn/courses/30/lessons/42885

문제 요약

2명까지만 탈 수 있는 구명보트에 사람을 태워 보낸다. 사람의 무게와 구명보트의 무게 상한이 주어지므로 최소 횟수를 구해 return한다.

문제 풀이

처음에는 인원 제한을 읽지 않아 풀이를 깊게 고민하다가, 2명 제한이라는 것을 보고 바로 풀 수 있던 문제이다.
가장 무거운 사람과 가장 가벼운 사람을 동시에 태울 수 없다면 가장 무거운 사람은 그 누구와도 함께 탈 수 없다.
그러므로 무거운 사람을 보내고, 남은 사람 중 가장 무거운 사람을 다시 데려와 계산을 하면 된다.
인원은 겨우 50k밖에 되지 않고 greedy하게 풀면 되기에 .data를 쓰지 않아도 될 것 같은 문제이다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

int solution ( vector < int > people , int limit )
{
    int iAnswer = 0 ;
    int * ipTemp ;
    int iLeftIndex = 0 ;
    int iRightIndex = people.size () - 1 ;



    std :: sort ( people.begin () , people.end () ) ;
    ipTemp = people.data () ;

    while ( iLeftIndex < iRightIndex )
    {
        if ( ipTemp [ iLeftIndex ] + ipTemp [ iRightIndex ] <= limit )            // Min + Max <= limit, save them
        {
            ++ iAnswer ;
            ++ iLeftIndex ;
            -- iRightIndex ;

            continue ;
        }

        // Min + Max > limit, so max must go

        -- iRightIndex ;
        ++ iAnswer ;
    }

    if ( iLeftIndex == iRightIndex )        // One person left
        ++ iAnswer ;



    return iAnswer ;
}