프로그래머스 : 구명보트 [C++]

문제 링크

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

 

문제 설명

1. 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다.
2. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
3. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

 

문제 입출력 예)

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

문제 풀이

• 우선적으로, people에 있는 데이터를 오름차순 정렬 하도록한다.
• people의 배열의 첫번째 값 + 배열의 마지막 값이 limit보다 작거나 같으면
• 구명보트에 태울 수 있는 무게에서 가장 이상적인 무게가 된다.
• 이를 토대로 프로그램을 작성하도록 한다.

1. sort()를 활용하여 people을 오름차순 정렬한다.
2. 배열의 마지막 값을 저장하고 pop_back() 한다.
3. 첫번째 값과, 마지막 값을 더하여 limit값과 비교한다.
4. limit 값보다 클 경우, 값에 1을 더해준다.
5. limit 값보다 작을 경우, 값에 1을 더해주고, 배열을 1 더해준다.

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

int solution(vector<int> people, int limit) {
    int idx = 0;
    int answer = 0;
    sort(people.begin(), people.end());
    
    while(people.size() > idx){
        int peopleBack = people.back();
        people.pop_back();
        if(people[idx] + peopleBack <= limit){
            answer++;
            idx++;
        }else{
            answer++;
        }
    }
    
    return answer;
}

 

 

 

리뷰

• push / pop을 잘 이용하도록 한다.