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

문제

---

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

프로그래머스

 

 

 

코드

---

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

using namespace std;
bool safe[500000];

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end(), greater<int>());
    int idx = people.size()-1;
    for(int i=0;i<people.size();i++){
        if(safe[i]) break;
        answer++;
        safe[i]=true;
        int temp = people[i];
        if(safe[idx]==false&&temp+people[idx]<=limit){
            safe[idx]=true;
            idx--;
        }
            
    }
    return answer;
}

 

 

 

풀이

---

'최대 2명씩 밖에 탈 수 없다'가 Point!

그렇다는건 즉 1명 혹은 2명이 탄다는 의미이고

1명밖에 타지 못한다는 것은 어느 누구와 타도 즉 남은 사람 중 가장 가벼운 사람과 타도 제한을 넘긴다는 의미!

 

 

여기서 착안한 아이디어

=> 남은 사람 중 가장 무거운 사람의 무게와 가장 가벼운 사람의 무게를 더해보자!

     1. 사람들을 무게 순으로 정렬한 뒤 가장 무거운 사람과 가장 가벼운 사람의 무게를 더한다.

     2. 만약 제한을 넘긴다면 무거운 사람은 혼자 타는 것밖에 답이 없으므로 혼자만 태워보낸다.

     3. 만약 제한을 넘기지 않는다면 둘이 타도 이상 없으므로 둘을 태워보낸다.

     4. 사람이 남지 않을 때까지 위의 과정을 계속 반복한다.

 

 

여기서 문제가 구명보트의 최소 개수를 구하는 것인데 3번처럼 해도 최소 개수가 나올 수 있는지 의문이 들 수 있다.

그러나 3번처럼 해도 답 나온다. 앞서 말한 point인 최대 2명이라는 제약 때문에.

예시를 들어 설명해보겠다.

 

 

ex)

limit: 100

people: 60, 40, 30, 10

 

만약에 위의 방법대로 태우지 않고 무게가 60인 사람과 30인 사람을 태워보낸다고 생각해보자.

애초에 무게가 60인 사람과 10인 사람을 태운다고 해도 제한을 넘기지 않는데 40과 10을 태운다고 문제가 생기진 않을 것이고 기대값은 2가 나온다.

그것은 반대로 60과10, 40과30을 태운다고 해도 문제가 생기지 않을 것이며 이 또한 기대값이 2가 나온다는 의미가 된다.

(60+30, 40+10) 이거나 (60+10, 40+30)

그냥 쉽게 생각해서 더 큰 수가 감당할 수 있는 수는 큰 수보다 작은 수들은 다 감당이 가능한데 2명이라는 제한으로 인해 무게가 낮은 걸 오름차순으로 생각하였을때 (1, 3), (2, 4)로 태우는 게 가능하다면 3과 4의 자리를 바꿔도 무방하다는 얘기.

즉 다른 방식이 가능하다고 할지언정 그 상황에서 탄 사람 위치를 위의 규칙처럼 바꾸어도 문제가 없다는 것이다.

 

 

고로 이와 같은 방식을 코드에 적용하였고, 다행히 통과!