softeer : 코딩 테스트 세트

https://softeer.ai/practice/6261

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

오늘도 열심히 삽질끝에 해냈다!

 

일단 이진탐색으로 해결을 봐야겠다는 것까지는 갔는데,,,,

또 자료형, min/max 초기값 설정에서 한참을 헤매다가 해결했다...^^.....;;

 

---

일단 단순하게 "하나의 코딩테스트 세트에는 1 ~ N 사이의 모든 난이도의 문제가 N개 있다. 서로 같은 문제를 포함하지 않는 코딩테스트 세트의 개수는?" 만 생각해보면,,,

 

level별로 문제가 3, 4, 5, 7, 2 개씩 있다고 생각해보면,,, 가능한 세트의 개수는 2이다!

즉 개수가 가장 "적은" 문제를 가진 레벨의 문제개수가 그대로 답이된다.

 

그러면 d배열도 포함해서 생각해보면,,, d배열 속 숫자들을 c배열에 적절히 추가해주어서, c배열 속 min값을 최대로 만들어주면 된다!!

 

근데,, 이걸 풀 때 적절히 넣어서 -> min을 최대로 만들자!! 로 접근하면 너무 어렵다!

반대로,, 최대 min을 정해두고, 가능한지 test를 통해 조절해보자! 로 접근해야 한다.

 

첫번재 예시인 2 2 1 1 3 을 생각해보자...

일단 C의 min인 1부터 시작해보면

 

세트개수가 1 : D 안써도 됨

세트개수가 2 : D[0]중 한개를 C[1]로 주거나, D[1]을 C[1]로 주면 됨

세트개수가 3 : D[0]중 하나는 C[0], 나머지 하나는 C[1], D[1]을 C[1]로 주면됨

세트개수가 4 : D[0]을 전부 C[0]으로 줘야하는데,,, 그 뒤에를 해결못한다.

=> 즉 정답은 3!!!

 

근데,,, 모든 테스트케이스를 이렇게 완전탐색으로 진행하면 너무 느리다!

(범위를 생각해보면,,,,)

 

그래서 세트개수를 가지고 이진탐색을 적용해준다.

 

가능한 세트개수의 최소값은,,, 기존 C배열의 min값이다.

가능한 세트개수의 최대값은,,, C[i] + D[i-1] + D[i] 값 중 max값이다!

 

이걸 초기값으로 해서 이진탐색을 돌려주면 해결된다.

 

 

 

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


using namespace std;



int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, t;
    cin >> n >> t;
    for(int i = 0; i<t; i++){

        long long min_answer;
        long long max_answer;
        
        vector<long long> c(n, 0);
        vector<long long> d(n-1, 0);
        for(int j = 0; j<n-1; j++){
            cin >> c[j];
            cin >> d[j];
        }
        cin >> c[n-1];

        min_answer = *min_element(c.begin(), c.end());
        
        max_answer = c[0] + d[0];
        for(int j = 1; j<n; j++){
            max_answer = max(c[j] + d[j-1] + d[j], max_answer);
        }

        max_answer++;

        // 이진탐색
        while(min_answer != max_answer){
            long long mid = (min_answer + max_answer + 1) / 2;
            long long now_c = c[0];
            
            bool flag = true;
            for(int j = 0; j<n-1; j++){
                if(now_c >= mid){
                    now_c = c[j+1] + d[j];
                }else if(now_c + d[j] >= mid){
                    now_c = c[j+1] + ((now_c + d[j]) - mid);
                }else{
                    flag = false;
                    break;
                }
            }
            
            if(now_c < mid){
                flag = false;
            }
            
            if(flag){
                min_answer = mid;
            }else{
                max_answer = mid - 1;
            }
        }

        
        cout << min_answer<<"\n";
        
    }

    

   return 0;
}