Codeforces Round #737 (Div. 2) B번

아이디어

• 그리디 알고리즘을 사용할 줄 안다

접근방식

1. 숫자값을 저장할 때, pair를 사용해서, {숫자의 값, 위치순서}를 저장해준다.
2. 숫자의 값대로 오름차순으로 sort 해준다
3. 연속으로 i번째 처음 순서 == i-1번째 처음 순서 + 1 이라면 같은 집합으로 묶을 수 있는 것으로 간주, 계속 집합을 묶어 가장 작은 개수로 만들 수 있는 집합의 개수를 구한다
4. 집합의 개수가 k보다 작거나 같으면 만들 수 있으므로(k보다 작다면 집합을 쪼개면 개수를 늘릴 수 있다) Yes 출력

#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <math.h>

using namespace std;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t; cin >> t;

    while(t--)
    {
        int n,k; cin >> n >> k;

        vector<pair<int,int>> v;

        for(int i=0;i<n;i++)
        {
            int num; cin >> num;
            v.push_back({num,i});
        }

        sort(v.begin(),v.end());

        int sub_cnt = 1;

        for(int i=1;i<n;i++)
        {
            if(v[i].second != v[i-1].second + 1) sub_cnt++;
        }

        if(sub_cnt <=k) cout << "Yes" <<endl;
        else cout <<"No" <<endl;


    }
    return 0;
}

평가

문제 풀이를 보고 벙찐 문제.
저는 처음에 위치 순서를 pair로 해서 sort하는 것 까진 구현하였으나, 이후 '각 집합을 무엇을 얼만큼 만드는지 어떻게 알아?'라고 계속 생각하다 구현을 실패하였습니다.
아무리 생각해도 순열, 조합으로는 시간복잡도가 너무 커질 것으로 예상되어 고민을 하다 다른 사람들의 힌트를 구하니
k를 꼭 완성해서 구현하는 것이 아닌, 'k보다 작은 개수의 집합이 가능하면 쪼개서 만들면 된다, 그 형태가 무엇이든' 이라는 아이디어를 얻었습니다.

꼭 구현을 완벽하게 해야한다는 제 사고방식을 많이 깨준 문제였습니다.

• 배울 것
  1) 꼭 완벽히 구현 할 필요 없다. 불가능 하다 판단되면 다른 방식을 빠르게 고안하자.