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

문제요약

무인도에 사람들이 갇혔습니다. 사람들의 무게 배열과 한 대의 구명보트가 견딜 수 있는 한계 무게가 주어집니다. 한 대의 구명보트에는 2명분의 자리밖에 없습니다. 단, 구명보트는 왕복을 하지 않고 사용하면 소멸합니다.

아이디어

그리디라는 문제 유형이 써있어서 빠르게 풀었던 것 같다..
사실 dp로 풀려고 했다 ㅎㅎㅋㅋㅋ..
1. 가장 작은 사람이랑 함께 타더라도 limit을 넘는 사람은 혼자 타야하는 게 자명하다.
2. limit 이하의 사람들 중에서 같이 탈 사람들을 고를 수 있다

이 때 고르는 기준은 작은 사람일 수록 큰 사람들이랑 같이 타줘야 2명이서 타는 보트의 수가 늘어난다는 것이다.(적당히 작은 사람과 적당히 큰 사람도 함께 탈 수 있게 된다.) 그래서 i 와 j 인덱스를 이용해서 양 끝에서 움직여 주면서 같이 탈 수 있는지 검사해주었다.
작은 사람이 귀하기 때문에 i는 한칸씩만 움직여줬고 j는 해당 v[i]와 같이 탈 수 있을 때까지 움직여줬다.

그리고 이렇게 작은 사람 - 큰 사람을 매칭시켜주다 보면 i랑 j가 같아지는 순간이 올 수도 있는데 이 땐 이 남은 한 명을 하나의 보트에 태우면 된다.

삽질

다행히 테케에 문제점을 알아차릴 케이스가 하나 있어서 수정하긴 했다.
서로 같이 탈 수 있는지 검사하는 for 문의 조건 절을 i!= j 로 했었는데 이렇게 하면 i = 3,j = 4 번 사람이 함께 탔을 때 i= 4, j = 3으로 바뀌면서 안 걸린다. i < j로 고쳐주었다.

코드

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    vector<int> people_remain;
    for(int i = 0;i<people.size();i++){
        if(people[i]>limit){
            answer++;
        }
        else{
            people_remain.push_back(people[i]);
        }
    }
    sort(people_remain.begin(),people_remain.end());
    
    int i = 0;
    int j = people_remain.size()-1;
    for(;i<j;j--){//뒤에서부터 앞으로 오는 포인터
        if(people_remain[i]+people_remain[j]<=limit){
            //cout<<"2개의 사람이 합쳐짐"<<i<<","<<j<<endl;
            i++;
        }
        answer++;
        //cout<<j<<","<<answer<<endl;
    }
    //i== j일 때 한 명 추가해줘야함
    if(i==j){
        answer++;
    }
    return answer;
}