[고득점Kit][그리디] 구명 보트 ⭐⭐

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[그리디] 구명보트

난이도 ⭐⭐

문제

내 풀이 ⭕

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    int i = 0;
    int j = people.size() - 1;
    
    while(true)
    {
        if (i == j)
        {
            answer++;
            break;
        }
        
        if (i > j)
            break;   
        
        if (people[i] + people[j] <= limit)
            i++;
        
        j--;
        
        answer++;
    }
    
    return answer;
}

• 우선 people 벡터를 오름차순 정렬 한다.
  • 사람들의 무게 순으로 정렬. 가장 가벼운 사람이 앞에, 무거울 수록 뒤에 위치하게 된다.
• 인덱스를 두개 사용했다.
  • i 벡터의 맨 앞부터 시작하여 증가하는 인덱스
  • j 벡터의 맨 뒤부터 시작하여 감소하는 인덱스

최대 2 명까지만 태울 수 있고, 보트를 최소한으로 써야 하므로 👉🏽 최대한 무거운 사람 중에서 함께 탈 사람을 찾아 봐야 한다.

• 예시 1
  • [40, 50], [70], [80] 👉 3 개
• 예시 2
  • [50], [70], [80] 👉 3 개
• 예시 3
  • [10, 90], [20, 80], [30, 70], [40, 60], [50] 👉 5 개
• 예시 4
  • [90], [80], [30, 70], [40, 60], [50] 👉 5 개

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기