프로그래머스, C++) Lv 2. 구명 보트

문제

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

프로그래머스

이 문제의 핵심

-> 그리디 알고리즘, 투 포인터

가장 무거운 사람과 가장 가벼운 사람을 같이 태워 구명보트를 보내야 최소가 됨.

---

원래 코드

보트에 사람이 있을 때, 없을 때를 기준으로 나눔

-> 사람을 건너뛰는 경우가 있어서 실패

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

using namespace std;


/*
최대 2명
무게 제한

5만 이하

입력: 사람의 몸무게, 보트의 limit
출력: 사용 보트의 최솟값

1) 2명을 태우는 경우
- 1명을 태운 후, 무게 제한이 40보다 위

2) 1명을 태우는 경우
- 1명을 태운 후, 무게 제한이 40보다 아래
*/

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    
    int tmpLimit = limit;
    bool isPinBoat = false;
    
    int i = 0;
    while(i<people.size())
    {
        // 보트에 사람이 없을 때
        if(isPinBoat == false)
        {
            // 1명을 태우고 무게가 남는다면
            if((tmpLimit - people[i]) >= 40)
            {
                tmpLimit -= people[i];
                isPinBoat = true;
            }
            // 1명을 태우고 무게가 남지 않는다면
            else
            {
                tmpLimit = limit;
                ++answer;
            }
        }
        // 보트에 사람이 있을 때
        else
        {
            // 1명을 태웠는데 다른 1명이 무게 초과일 때
            if(people[i] > tmpLimit)
            {
                answer +=2;
            }
            // 2명을 태울 때
            else
            {
                answer++;
            }
            tmpLimit = limit;
            isPinBoat = false;
        }
        ++i;
    }
    
    
    return answer;
}

 

---

투 포인터를 사용한 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());
    int l = 0, r = (int)people.size() - 1;
    int boats = 0;

    while (l <= r) {
        // 가장 무거운 r은 반드시 태움
        if (people[l] + people[r] <= limit) {
            // 가벼운 l과 같이 탈 수 있으면 함께 보냄
            ++l;
            --r;
        } else {
            // 같이 못 타면 r 혼자 보냄
            --r;
        }
        ++boats;
    }
    return boats;
}