lv 2) 구명 보트 (with 투포인터, 슬라이딩 윈도우 활용 용도) [다시]

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

프로그래머스

 

 

슬라이딩 윈도우는 연속된 구간을 다룰 때 쓰는 기법이라 해당 문제에 맞지 않은 풀이.

이 문제는 연속되지 않은 최적 조합을 찾아야 하기 때문에 투포인터가 적합하다.

 

 

그리디문제

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

//투포인터 사용
//첫 인덱스와 끝 인덱스 부터 더해서
// limit을 넘을 경우 끝 인덱스는 혼자 보트에 태우며, right --
// limit이 넘지 않을 경우 둘다 하나의 보트에 태우며, left++, right --
// left 값이 right값을 초과할 때 loop 빠져나오기
int solution(vector<int> people, int limit) {
    int answer = 0;
    int left = 0;
    int right = people.size() - 1;
    int sum = 0;
 
    sort(people.begin(), people.end());
    while(left <= right){
        sum = people[left] + people[right];
        if(sum > limit){
            answer++;
            right--;
        }
        else{
            answer++;
            left++;
            right--;
        }
    }
    return answer;
}

 

 

 

누적합 (틀림)

틀린 이유: 구명보트 한번에 최대 2명씩밖에 탈 수 있다란 조건. 

(해당 조건을 간과하고, limit까지 최대한 인원을 구명보트에 태울 수 있는 최소 보트 값을 구했다.)

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int sum = 0;
    for(int idx = 0; idx < people.size(); ++idx){
        sum += people[idx];
        if(sum > limit){
            sum  = people[idx];
            answer++;
        }
    }   
    answer+=1; // 마지막 보트
    return answer;
}