Programmers_Level2_구명보트

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

프로그래머스

 

---

 

 

무게 제한이 있는 구명 보트에 최대 2명씩 태워서 사람들을 모두

구출하는 최소한의 구명보트 사용 횟수를 구하는 문제이다. 

 

처음에는 브루트포스로 모든 경우의 수를 구해야하나 하다가 

구명보트에 최소 2명밖에 타지 못한다는 것과 

무게 제한이 있다는 것을 가지고 투포인터로 문제를 풀었다.

 

사람들을 무게로 정렬 시킨다. 

head를 가벼운 사람으로 tail을 무거운 사람으로 지정하고

가장 가벼운 사람과 가장 무거운 사람의 무게의 합을 구명 보트의 무게 제한과 비교하였다. 

 

무게 제한을 넘는다면 무거운 사람은 혼자 탈 수 밖에 없으므로 tail을 --한다. 

만약 두사람의 무게가 무게 제한 보다 가볍다면 둘이서 탈 수 있는 것으로

head는 ++로 tail은 --로 이동한다. 

 

그렇게 이동 하다보면 head가 tail을 지나는 순간이 오면 모두가 탈출한 것이다. 

 

구현 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class lifeboat
{
    private: 
    vector<int> people;
    int limit;

    public : 
    lifeboat(vector<int> people, int limit)
    {
        this->people = people;
        this->limit = limit;
        sort(this->people.begin(), this->people.end());
    }
    int answer = 0;
    int calculateBoat();
};

int lifeboat::calculateBoat()
{
    int head = 0;
    int tail = people.size() - 1;

    while(head <= tail)
    {
        if(people[head] + people[tail] <= limit)
        {
            head++;
            tail--;
        }
        else
        {
            tail--;
        }
        answer++;
    }
    return answer;
}


int solution(vector<int> people, int limit) {
    lifeboat myLifeboat(people, limit);
    
    int answer = myLifeboat.calculateBoat();
    return answer;
}