softeer : 마이크로서버

https://softeer.ai/class/devcrew/study/resource/detail/description/6264?id=280&resourceId=328

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

쉬운줄 알았는데 어렵다...

 

처음에는 그냥 무조건 정렬해두고 투포인터로 풀었다 (양쪽부터 최대한 많이 묶기)

 

근데!! 300 300 300 을 그냥 900으로 묶는게 더 좋은 방법인 상황이 있었다

    300 300 300 300 300 300 450 450 생각해보기

 

그렇다고 300 3개가 있을 때 무조건 묶는게 좋은가?? 라고 생각해보면.... 그것도 아니다!

    300 300 300 500 500 500 생각해보기

 

그래서... 잘 생각을 해야한다!

 

1. 일단 300은 따로 빼둔다 (3개를 묶을 지, 다른애랑 2개로 보낼지 상황판단을 해야한다)

2. 300을 제외한 애들을 가지고 투 포인터로 확인을 하는데.,.,.... (i : 작은쪽, j : 큰쪽)

    2-a : [j] > 600

             600보다 큰 애는 무조건 혼자 보내야함 (왜냐면,,, 마이크로 하나의 최소가 300이므로)

    2-b : [i] + [j] <= 900

             오우 두개 묶을 수 있으니까 묶어준다!

    2-c : else (두개 묶어서 보내지는 못하고, [j]가 600을 넘기지 않음)

             [j]랑 300이랑 묶어서 보내줄 수 있다!

             i는 계속 증가하므로, 앞으로 남은 [i]는 무조건 더 커질수밖에 없다 (남은 애들이랑 [j]랑 어짜피 못묶음)

             [j]를 혼자 보내는것보다 300이랑 묶어서 보내준다!

3. 남은 300은, 최대한 3개씩 묶어본다!

 

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

int sol(vector<int> vec){
    
    int answer = 0;

    // 300 count
    int cnt300 = 0;
    for(int i = 0; i<vec.size(); i++){
        if(vec[i] != 300){
            break;
        }
        cnt300++;
    }

    // 300을 제외한 애들부터 확인해보기
    // -> 무조건 1개아님 2개만 묶을 수 있음!
    int j = vec.size()-1;
    for(int i = cnt300; i<vec.size(); i++){
        if(i > j){
            break;
        }
        // 큰쪽이 600보다 큼 == 무조건 혼자 보내야함
        if(vec[j] > 600){
            answer++;
            j--;
            i--;
            continue;
        }
        if((i != j) && (vec[i] + vec[j] <= 900)){
        // 합쳐보니 900아래임 == 두개 묶어주기
            
            answer++;
            j--;
            continue;
        }
        
        
        // 두 경우 다 아님 == 합쳤을때 900을 넘기는데, 큰쪽이 600보다 작음 == 큰쪽이랑 300이랑 묶어서 내보내기!
            
            answer++;
            j--;
            i--;
            if(cnt300 > 0){
                cnt300--;
            }
            
        
    }
    answer += (cnt300/3);
    if((cnt300%3) > 0){
        answer++;
    }
    
    return answer;
}

int main(int argc, char** argv)
{
    int t;
    cin >> t;
    for(int i = 0; i<t; i++){
        int n;
        cin >> n;
        vector<int> services;
        for(int j = 0; j<n; j++){
            int temp;
            cin >> temp;
            services.push_back(temp);
        }
        if(n == 1){
            cout << "1\n";
            continue;
        }
        sort(services.begin(), services.end());
        cout << sol(services)<<"\n";
        
        
    }

   return 0;
}