문제 푼 날짜 : 2021-08-14

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42885

접근 및 풀이

처음엔 몸무게를 오름차순으로 정렬하여 작은 순서대로 보트에 무게 제한을 체크하며 넣어주도록 하였다.
하지만 이렇게 하면 몸무게가 [50, 50, 70, 70] 인 사람들이 있을 때, 무게 제한이 120kg 이면 답이 3이 나와버린다.(정답은 2가 되어야한다.)
그래서 몸무게가 가장 가벼운 사람과 가장 무거운 사람끼리 보트에 태워나가야 하겠구나라고 생각하며 구현했지만,,
계속해서 통과하지 못하고, 한 시간동안 삽질을 거듭하다가 문제의 조건에서 보트에 한 번에 2명씩 밖에 못 탄다는 조건을 발견하고 좌절하였다...
무게 제한 내에 최대한 태우는 문제인줄 알고... 혼자 문제를 만들어서 풀어 버렸다... 하아...

코드(틀림)

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    stack<int> st;
    sort(people.begin(), people.end());
    
    int now = 0;
    for (auto a : people) {
        if (st.empty()) {
            st.push(a);
        } else {
            if (st.top() + a <= limit) {
                int tmp = st.top() + a;
                st.pop();
                st.push(tmp);
            } else {
                st.push(a);
            }
        }
    }
    return st.size();
}

코드(통과)

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

using namespace std;

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

결과

피드백

문제가 쉬워보인다고 건성건성 읽지말고, 꼼꼼히 잘 읽자...